Submission #2936856
Source Code Expand
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
void Read(int &p)
{
p=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
p=p*10+c-'0',c=getchar();
}
const int MAXN=102018;
int N,k,root,u,v,val[MAXN],eoro[MAXN];
bool vis[MAXN],ol[MAXN];
vector<int> G[MAXN];
vector<int> C[MAXN];
bool build_tree(int p)
{
vis[p]=1;
for(unsigned int i=0;i<G[p].size();i++)
{
int t=G[p][i];
if(!vis[t])
{
C[p].push_back(t);
if(eoro[t]!=-1 && eoro[t]==eoro[p]) return 1;
eoro[t]=(eoro[p]+1)%2;
bool o=build_tree(t);
if(o) return 1;
}
}
return 0;
}
bool ed;
void draw(int p)
{
if(ed) return;
if(C[p].size()==0)
{
bool cnt=0;
for(int i=1;i<=N && !cnt;i++)
if(val[i]==-1) cnt=1;
if(!cnt)
{
for(int i=1;i<=N;i++)
printf("%d\n",val[i]);
ed=1;
}
return ;
}
for(unsigned int i=0;i<C[p].size() && !ed;i++)
{
int t=C[p][i];
if(ol[t])
{
if(val[t]-val[p]>1 || val[p]-val[t]>1)
{
if(ol[p]) ed=1,puts("No");
return ;
}
else draw(t);
continue;
}
val[t]=val[p]+1,draw(t);
if(val[t]>=1) val[t]=val[p]-1,draw(t);
}
if(ed) return ;
}
int main()
{
memset(eoro,-1,sizeof eoro);
memset(val,-1,sizeof val);
Read(N);
for(int i=2;i<=N;i++)
Read(u),Read(v),G[u].push_back(v),G[v].push_back(u);
Read(k);
Read(root),Read(val[root]),eoro[root]=val[root]%2,ol[root]=1;
for(int i=2;i<=k;i++)
Read(u),Read(v),val[u]=v,eoro[u]=v%2,ol[u]=1;
if(build_tree(root)) ed=1,puts("No");
else draw(root);
if(!ed) puts("No");
}
Submission Info
Submission Time |
|
Task |
C - 1D Reversi |
User |
Crloss |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1673 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
5760 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
alternate_01.txt, alternate_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, same_01.txt, same_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt |
Case Name |
Status |
Exec Time |
Memory |
alternate_01.txt |
TLE |
2103 ms |
5760 KB |
alternate_02.txt |
TLE |
2103 ms |
5760 KB |
random_01.txt |
TLE |
2103 ms |
5760 KB |
random_02.txt |
TLE |
2103 ms |
5760 KB |
random_03.txt |
TLE |
2103 ms |
5760 KB |
random_04.txt |
TLE |
2103 ms |
5760 KB |
random_05.txt |
TLE |
2103 ms |
5760 KB |
same_01.txt |
TLE |
2103 ms |
5760 KB |
same_02.txt |
TLE |
2103 ms |
5760 KB |
sample_01.txt |
TLE |
2103 ms |
5760 KB |
sample_02.txt |
TLE |
2103 ms |
5760 KB |
sample_03.txt |
TLE |
2103 ms |
5760 KB |
small_01.txt |
TLE |
2103 ms |
5760 KB |
small_02.txt |
TLE |
2103 ms |
5760 KB |
small_03.txt |
TLE |
2103 ms |
5760 KB |