Submission #1039412

#TimeUsernameProblemLanguageResultExecution timeMemory
1039412vnm06Werewolf (IOI18_werewolf)C++14
100 / 100
580 ms164552 KiB
#include<bits/stdc++.h> #include "werewolf.h" using namespace std; int n, m, q; int fenw[400005]; void update(int pos) { pos++; //cout<<"upd "<<pos<<endl; while(pos<=n+2) { fenw[pos]++; pos+=(pos&(-pos)); } } int query(int pos) { int res=0; while(pos) { res+=fenw[pos]; pos-=(pos&(-pos)); } return res; } int query(int le, int ri) { le++; ri++; //cout<<le<<" "<<ri<<" "<<query(ri)-query(le-1)<<endl; return query(ri)-query(le-1); } int brcomp=0; vector<int> compn[400005], gr[400005]; int nom_comp[400005], par[400005], par_comp[400005]; int new_nom[400005], tek_nom=1; int be_id[400005], en_id[400005]; vector<int> spis_1[400005], spis_2[400005]; int tree_1[20][400005], tree_2[20][400005]; void build_tree_1() { for(int j=n-1; j>=0; j--) tree_1[0][j]=par[j]; for(int j=n-1; j>=0; j--) { if(par[j]!=-1) spis_1[par[j]].push_back(j); } for(int lvl=1; lvl<20; lvl++) { for(int v=0; v<n; v++) { if(tree_1[lvl-1][v]==-1) tree_1[lvl][v]=-1; else tree_1[lvl][v]=tree_1[lvl-1][tree_1[lvl-1][v]]; } } } void build_tree_2() { for(int j=n-1; j>=0; j--) tree_2[0][j]=par[j]; for(int j=n-1; j>=0; j--) { if(par[j]!=-1) spis_2[par[j]].push_back(j); } for(int lvl=1; lvl<20; lvl++) { for(int v=0; v<n; v++) { if(tree_2[lvl-1][v]==-1) tree_2[lvl][v]=-1; else tree_2[lvl][v]=tree_2[lvl-1][tree_2[lvl-1][v]]; } } } int be[400005], en[400005]; void renumerate(int v) { new_nom[v]=tek_nom; be[v]=tek_nom; tek_nom++; int brs=spis_1[v].size(); for(int i=0; i<brs; i++) { renumerate(spis_1[v][i]); } en[v]=tek_nom-1; } int brv=0; vector<int> Eut; int fir[400005], las[400005]; void euler_tour(int v) { Eut.push_back(v); fir[v]=brv; las[v]=brv; brv++; int brs=spis_2[v].size(); for(int i=0; i<brs; i++) { euler_tour(spis_2[v][i]); Eut.push_back(v); las[v]=brv; brv++; } } int ans[400005]; vector<int> id_beg[400005], id_las[400005]; std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { q=S.size(); n=N; m=X.size(); for(int i=0; i<m; i++) { gr[X[i]].push_back(Y[i]); gr[Y[i]].push_back(X[i]); } memset(par, -1, sizeof(par)); memset(nom_comp, -1, sizeof(nom_comp)); for(int j=n-1; j>=0; j--) { compn[brcomp].push_back(j); nom_comp[j]=brcomp; par_comp[brcomp]=j; brcomp++; int brs=gr[j].size(); for(int i=0; i<brs; i++) { int nv=gr[j][i]; if(nv<j || nom_comp[j]==nom_comp[nv]) continue; par[par_comp[nom_comp[nv]]]=j; if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size()) { int old_comp=nom_comp[nv]; for(int k=0; k<compn[old_comp].size(); k++) { int tv=compn[old_comp][k]; nom_comp[tv]=nom_comp[j]; compn[nom_comp[j]].push_back(tv); } par_comp[nom_comp[j]]=j; compn[old_comp].resize(0); } else { int old_comp=nom_comp[j]; for(int k=0; k<compn[old_comp].size(); k++) { int tv=compn[old_comp][k]; nom_comp[tv]=nom_comp[nv]; compn[nom_comp[nv]].push_back(tv); } par_comp[nom_comp[j]]=j; compn[old_comp].resize(0); } } //for(int i=0; i<n; i++) cout<<nom_comp[i]<<" "; //cout<<endl; } build_tree_1(); for(int i=0; i<=brcomp+2; i++) {compn[i].resize(0); nom_comp[i]=-1; par[i]=par_comp[i]=-1;} brcomp=0; for(int j=0; j<n; j++) { compn[brcomp].push_back(j); nom_comp[j]=brcomp; par_comp[brcomp]=j; brcomp++; int brs=gr[j].size(); for(int i=0; i<brs; i++) { int nv=gr[j][i]; if(nv>j || nom_comp[j]==nom_comp[nv]) continue; par[par_comp[nom_comp[nv]]]=j; if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size()) { int old_comp=nom_comp[nv]; for(int k=0; k<compn[old_comp].size(); k++) { int tv=compn[old_comp][k]; nom_comp[tv]=nom_comp[j]; compn[nom_comp[j]].push_back(tv); } par_comp[nom_comp[j]]=j; compn[old_comp].resize(0); } else { int old_comp=nom_comp[j]; for(int k=0; k<compn[old_comp].size(); k++) { int tv=compn[old_comp][k]; nom_comp[tv]=nom_comp[nv]; compn[nom_comp[nv]].push_back(tv); } par_comp[nom_comp[j]]=j; compn[old_comp].resize(0); } } } build_tree_2(); renumerate(0); euler_tour(n-1); for(int i=0; i<q; i++) { for(int lvl=19; lvl>=0; lvl--) { if(tree_1[lvl][S[i]]==-1) continue; else if(tree_1[lvl][S[i]]>=L[i]) S[i]=tree_1[lvl][S[i]]; } for(int lvl=19; lvl>=0; lvl--) { if(tree_2[lvl][E[i]]==-1) continue; else if(tree_2[lvl][E[i]]<=R[i]) E[i]=tree_2[lvl][E[i]]; } //cout<<S[i]<<' '<<E[i]<<endl; if(fir[E[i]]) id_beg[fir[E[i]]-1].push_back(i); id_las[las[E[i]]].push_back(i); //cout<<fir[E[i]]<<" "<<las[E[i]]<<endl; } ///for(int i=0; i<n; i++) //////cout<<fir[i]<<" "<<las[i]<<" "; ////cout<<endl; //for(int i=0; i<n; i++) cout<<new_nom[i]<<" "; //cout<<endl; //for(int i=0; i<n; i++) cout<<tree_1[0][i]<<" "; //cout<<endl; int totbr1=0, totbr2=0; for(int i=0; i<Eut.size(); i++) { update(new_nom[Eut[i]]); //cout<<new_nom[Eut[i]]<<endl; ////cout<<new_nom[Eut[i]]<<" "; for(int j=0; j<id_beg[i].size(); j++) { ans[id_beg[i][j]]-=query(be[S[id_beg[i][j]]], en[S[id_beg[i][j]]]); totbr1++; ////cout<<id_beg[i][j]<<" "<<be[S[id_beg[i][j]]]<<" "<<en[S[id_beg[i][j]]]<<endl; } for(int j=0; j<id_las[i].size(); j++) { ans[id_las[i][j]]+=query(be[S[id_las[i][j]]], en[S[id_las[i][j]]]); ////cout<<"op "<<ans[0]<<" "<<be[S[id_las[i][0]]]<<" "<<en[S[id_las[i][0]]]<<endl; totbr2++; //////cout<<id_las[i][j]<<" "<<be[S[id_las[i][j]]]<<" "<<en[S[id_las[i][j]]]<<endl; } } vector<int> A; A.resize(q); for(int i=0; i<q; i++) A[i]=bool(ans[i]); return A; } /** 15 14 1 10 8 8 13 13 3 3 12 12 4 4 2 2 6 6 7 7 5 5 0 0 1 1 14 14 9 9 11 3 4 0 5 (10 8 13) 3 (12 4) 2 (6 7 5) 0 1 (14 9 11) */

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:209:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:250:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |   for(int i=0; i<Eut.size(); i++)
      |                ~^~~~~~~~~~~
werewolf.cpp:255:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |     for(int j=0; j<id_beg[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~
werewolf.cpp:261:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |     for(int j=0; j<id_las[i].size(); 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...