Submission #131897

#TimeUsernameProblemLanguageResultExecution timeMemory
131897dndhk족보 (KOI18_family)C++14
0 / 100
18 ms14584 KiB
#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], mlv[MAX_N+1]; void init(int x){ for(int i=0; i<x; i++){ g[i] = l[i] = r[i] = i; mlv[i] = INF; } } 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]; mlv[x] = min(mlv[x], mlv[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 : min(T[1].lv[T[1].lca(vt[g1-1].second, vt[g1].second)], min(mlv[find_g(i1)], mlv[find_g(i2)])); l3 = (r[g2]==K-1) ? 0 : min(T[1].lv[T[1].lca(vt[r[g2]].second, vt[r[g2]+1].second)], min(mlv[find_g(i1)], mlv[find_g(i2)])); 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)]; //cout<<n1<<" "<<n2<<endl; //cout<<l1<<" "<<l2<<" "<<l3<<" "<<l4<<" "<<l5<<" "<<l6<<endl; if((l3>l1 && l4!=l6) || (l2>l1 && l4!=l5)){ printf("NO"); return 0; } mlv[find_g(i1)] = min(mlv[find_g(i1)], l1); union_g(i1, i2); } printf("YES"); return 0; }

Compilation message (stderr)

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:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size()-1; i++){
               ~^~~~~~~~~~~~
family.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<upd.size(); i++){
               ~^~~~~~~~~~~
family.cpp:88: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:91: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...