| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65174 |
2018-08-06T23:46:43 Z |
gs18115 |
None (KOI18_family) |
C++14 |
|
18 ms |
16888 KB |
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1e9;
const int MAXN=3e5+10;
vector<int>adj[2][MAXN];
bool vi[MAXN];
int K,i,j;
int root[2],N[2];
int pa[2][MAXN],leaf[2][MAXN];
int lev[MAXN],sz[MAXN],par[MAXN];
int chk[MAXN];
int cnt;
int parent(int x)
{
if(par[x]==-1)
return x;
return par[x]=parent(par[x]);
}
void Union(int x,int y)
{
int X=parent(x);
int Y=parent(y);
if(X==Y)
return;
if(lev[X]>lev[Y])
{
par[Y]=X;
sz[X]+=sz[Y];
}
else if(lev[Y]>lev[X])
{
par[X]=Y;
sz[Y]+=sz[X];
lev[Y]++;
}
else if(sz[X]>sz[Y])
{
par[Y]=X;
sz[X]+=sz[Y];
lev[X]++;
}
else
{
par[X]=Y;
sz[Y]+=sz[X];
}
return;
}
struct NODE
{
int sz,lv;
int tree,node;
}tree[2][MAXN];
vector<NODE>sorting;
bool cmp(NODE a,NODE b)
{
return a.sz!=b.sz?a.sz<b.sz:a.lv>b.lv;
}
void pc(int t,int h)
{
if(vi[h])
return;
vi[h]=true;
if(pa[t][h]!=-1)
{
adj[t][pa[t][h]].push_back(h);
pc(t,pa[t][h]);
}
return;
}
pair<int,int>dfs(int t,int h,int lv)
{
tree[t][h].lv=lv;
tree[t][h].tree=t;
tree[t][h].node=h;
if(adj[t][h].empty())
{
leaf[t][h]=h;
tree[t][h].sz=1;
return make_pair(h,1);
}
pair<int,int>P;
P=dfs(t,adj[t][h][0],lv+1);
leaf[t][h]=P.first;
int s=P.second;
for(int i=1;i<adj[t][h].size();i++)
{
P=dfs(t,adj[t][h][i],lv+1);
s+=P.second;
}
tree[t][h].sz=s;
return make_pair(leaf[t][h],tree[t][h].sz);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>N[0]>>N[1]>>K;
for(i=0;i<N[0];i++)
{
cin>>pa[0][i];
if(pa[0][i]==0)
root[0]=i;
pa[0][i]--;
}
for(i=0;i<N[1];i++)
{
cin>>pa[1][i];
if(pa[1][i]==0)
root[1]=i;
pa[1][i]--;
}
fill(vi,vi+N[0],false);
for(i=0;i<K;i++)
pc(0,i);
fill(vi,vi+N[1],false);
for(i=0;i<K;i++)
pc(1,i);
dfs(0,root[0],0);
dfs(1,root[1],0);
for(i=0;i<2;i++)
for(j=K;j<N[i];j++)
sorting.push_back(tree[i][j]);
sort(sorting.begin(),sorting.end(),cmp);
fill(par,par+MAXN,-1);
fill(sz,sz+MAXN,1);
for(i=0;i<sorting.size();i++)
{
NODE X=sorting[i];
cout<<X.tree<<' '<<X.node<<' '<<X.sz<<' '<<X.lv<<endl;
for(j=0;j<adj[X.tree][X.node].size();j++)
{
int Y=adj[X.tree][X.node][j];
Union(leaf[X.tree][X.node],leaf[X.tree][Y]);
}
if(sz[parent(leaf[X.tree][X.node])]!=X.sz)
return cout<<"NO",0;
}
cout<<"YES";
return 0;
}
Compilation message
family.cpp: In function 'std::pair<int, int> dfs(int, int, int)':
family.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<adj[t][h].size();i++)
~^~~~~~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:130:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<sorting.size();i++)
~^~~~~~~~~~~~~~~
family.cpp:134:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<adj[X.tree][X.node].size();j++)
~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
