| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131734 |
2019-07-17T13:42:57 Z |
dndhk |
None (KOI18_family) |
C++14 |
|
14 ms |
14584 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 300000;
const int MAX_K = 20;
int K;
struct Tree{
int N, r;
int p[MAX_N+1];
bool vst[MAX_N+1];
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], par[MAX_N+1][MAX_K+1], in[MAX_N+1], out[MAX_N+1], cnt = 0;
void dfs(int x){
if(p[x]==0) cnt = 0;
in[x] = ++cnt; vst[x] = true; lv[x] = (p[x]==0 ? 1 : lv[p[x]]+1);
par[x][0] = p[x];
for(int i=1; i<=MAX_K; i++) par[x][i] = par[par[x][i-1]][i-1];
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]==p[x]) continue;
p[gp[x][i]] = x;
dfs(gp[x][i]);
}
out[x] = cnt;
}
int lca(int x, int y){
for(int i=MAX_K; i>=0; i--){
if(lv[par[x][i]]>=lv[y]) x = par[x][i];
if(lv[par[y][i]]>=lv[x]) y = par[y][i];
}
for(int i=MAX_K; i>=0; i--){
if(par[x][i]!=par[y][i]){
x = par[x][i]; y = par[y][i];
}
}
if(x!=y) x = par[x][0];
return x;
}
};
Tree T[2];
vector<pii> vt;
vector<pii> upd;
int g[MAX_N+1], l[MAX_N+1], r[MAX_N+1];
void init(int x){
for(int i=0; i<x; i++){
g[i] = l[i] = r[i] = i;
}
}
int find_g(int x){
return (x==g[x]) ? x : g[x] = find_g(g[x]);
}
void union_g(int x, int y){
x = find_g(x); y = find_g(y);
if(x>y) {int tmp = x; x = y; y = tmp;}
g[y] = x;
r[x] = r[y];
}
bool in[MAX_N+1];
int main(){
scanf("%d%d%d", &T[0].N, &T[1].N, &K);
for(int i=0; i<2; i++){
for(int j=1; j<=T[i].N; j++){
scanf("%d", &T[i].p[j]);
if(T[i].p[j]==0) T[i].r = j;
else if(i==0) T[i].gp[T[i].p[j]].pb(j);
}
if(i==0) T[i].dfs(T[i].r);
}
for(int i=1; i<=K; i++) vt.pb({T[0].in[i], i});
sort(vt.begin(), vt.end());
for(int i=0; i<K; i++){
int n = vt[i].second;
//cout<<n<<" ";
while(1){
if(in[n]) break;
in[n] = true;
if(T[1].p[n]==0) break;
T[1].gp[T[1].p[n]].pb(n);
n = T[1].p[n];
}
}
T[1].dfs(T[1].r);
while(!vt.empty()) vt.pop_back();
for(int i=1; i<=K; i++) vt.pb({T[1].in[i], i});
for(int i=1; i<=T[0].N; i++){
T[0].gp[i].clear();
in[i] = false;
}
sort(vt.begin(), vt.end());
//cout<<endl;
for(int i=0; i<K; i++){
int n = vt[i].second;
//cout<<n<<" ";
while(1){
if(in[n]) break;
in[n] = true;
if(T[0].p[n]==0) break;
T[0].gp[T[0].p[n]].pb(n);
n = T[0].p[n];
}
}
T[0].dfs(T[0].r);/*
cout<<endl;
for(int i=1; i<=K; i++){
cout<<T[0].in[i]<<" ";
}
cout<<endl;
for(int i=0; i<K; i++){
cout<<vt[i].second<<" ";
}*/
for(int i=0; i<K-1; i++){
if(T[0].in[vt[i].second] > T[0].in[vt[i+1].second]){
printf("NO"); return 0;
}if(T[1].in[vt[i].second] > T[1].in[vt[i+1].second]){
printf("NO"); return 0;
}
}
for(int i=0; i<vt.size()-1; i++){
int n1 = vt[i].second, n2 = vt[i+1].second;
upd.pb({-T[0].lv[T[0].lca(n1, n2)], i});
}
sort(upd.begin(), upd.end());
init(K);
int i1, i2, n1, n2, g1, g2, l1, l2, l3, l4, l5, l6;
for(int i=0; i<upd.size(); i++){
i1 = upd[i].second; i2 = upd[i].second+1;
n1 = vt[i1].second; n2 = vt[i2].second;
g1 = find_g(i1); g2 = find_g(i2);
l1 = T[1].lv[T[1].lca(n1, n2)];
l2 = (g1==0) ? 0 : T[1].lv[T[1].lca(vt[g1-1].second, vt[g1].second)];
l3 = (r[g2]==K-1) ? 0 : T[1].lv[T[1].lca(vt[r[g2]].second, vt[r[g2]+1].second)];
l4 = T[0].lv[T[0].lca(n1, n2)];
l5 = (g1==0) ? INF : T[0].lv[T[0].lca(vt[g1-1].second, vt[g1].second)];
l6 = (r[g2]==K-1) ? INF : T[0].lv[T[0].lca(vt[r[g2]].second, vt[r[g2]+1].second)];
if(l3>l1 || l2>l1 || (l3==l1 && l4!=l6) || (l1==l2 && l4!=l5)){
printf("NO");
return 0;
}
union_g(i1, i2);
}
printf("YES");
return 0;
}
Compilation message
family.cpp: In member function 'void Tree::dfs(int)':
family.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<vt.size()-1; i++){
~^~~~~~~~~~~~
family.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<upd.size(); i++){
~^~~~~~~~~~~
family.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &T[0].N, &T[1].N, &K);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &T[i].p[j]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
