Submission #305080

#TimeUsernameProblemLanguageResultExecution timeMemory
305080oleh1421Werewolf (IOI18_werewolf)C++17
15 / 100
4075 ms88480 KiB
#define SYS #ifdef SYS #include "werewolf.h" #endif // SYS #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=300010; int p[N]; int q[N]; int a[N]; int b[N]; int dsu[N]; int get(int x){ if (x==dsu[x]) return x; return get(dsu[x]); } vector<int>cmp[N]; vector<int>g[N]; vector<pair<int,int> >qS[N]; vector<pair<int,int> >qE[N]; int La[N]; int Ra[N]; int Lb[N]; int Rb[N]; int dsu1[N]; int mn[N]; int mx[N]; int get1(int x){ if (dsu1[x]==x) return x; return dsu1[x]=get1(dsu1[x]); } vector<int> check_validity(int N, vector<int> X, std::vector<int> Y,vector<int> S,vector<int> E,vector<int> L, vector<int> R) { int Q = S.size(); vector<int> Ans(Q,0); for (int i=0;i<X.size();i++){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } for (int i=0;i<N;i++) dsu[i]=i,cmp[i]={i},p[i]=0; for (int i=N-1;i>=0;i--){ for (int to:g[i]){ if (to<i) continue; int x=get(i); int y=get(to); if (x==y) continue; if (cmp[x].size()>cmp[y].size()) swap(x,y); for (int v:cmp[x]){ p[v]+=cmp[y].size(); } for (int v:cmp[x]){ cmp[y].push_back(v); } cmp[x].clear(); dsu[x]=y; } } for (int i=0;i<N;i++) dsu[i]=i,cmp[i]={i},q[i]=0; for (int i=0;i<N;i++){ for (int to:g[i]){ if (to>i) continue; int x=get(i); int y=get(to); if (x==y) continue; // cout<<"edge: "<<to<<" "<<i<<" "<<x<<" "<<y<<" "<<cmp[x].size()<<" "<<cmp[y].size()<<endl; if (cmp[x].size()>cmp[y].size()) swap(x,y); for (int v:cmp[x]){ q[v]+=cmp[y].size(); } for (int v:cmp[x]){ cmp[y].push_back(v); } cmp[x].clear(); dsu[x]=y; } // for (int j=0;j<N;j++) cout<<q[j]<<" "; // cout<<endl; } for (int i=0;i<N;i++){ // cout<<p[i]<<" "<<q[i]<<endl; a[p[i]]=i; b[q[i]]=i; } // for (int i=0;i<N;i++) cout<<a[i]<<" "; // cout<<endl; // for (int i=0;i<N;i++) cout<<b[i]<<" "; // cout<<endl; for (int i=0;i<Q;i++){ qS[L[i]].push_back({S[i],i}); qE[R[i]].push_back({E[i],i}); } for (int i=0;i<N;i++){ dsu1[i]=i; mn[i]=p[i]; mx[i]=p[i]; } for (int i=N-1;i>=0;i--){ for (int to:g[i]){ if (to<i) continue; int x=get1(i); int y=get1(to); if (x==y) continue; mn[y]=min(mn[y],mn[x]); mx[y]=max(mx[y],mx[x]); dsu1[x]=y; } for (auto cur:qS[i]){ La[cur.second]=mn[get1(cur.first)]; Ra[cur.second]=mx[get1(cur.first)]; } } for (int i=0;i<N;i++){ dsu1[i]=i; mn[i]=q[i]; mx[i]=q[i]; } for (int i=0;i<N;i++){ for (int to:g[i]){ if (to>i) continue; int x=get1(i); int y=get1(to); if (x==y) continue; mn[y]=min(mn[y],mn[x]); mx[y]=max(mx[y],mx[x]); dsu1[x]=y; } for (auto cur:qE[i]){ Lb[cur.second]=mn[get1(cur.first)]; Rb[cur.second]=mx[get1(cur.first)]; } } for (int i=0;i<Q;i++){ Ans[i]=0; set<int>st; for (int j=La[i];j<=Ra[i];j++){ st.insert(a[j]); } for (int j=Lb[i];j<=Rb[i];j++){ if (st.find(b[j])!=st.end()) Ans[i]=1; } } return Ans; } #include <cstdio> #include <cstdlib> #include <vector> #ifndef SYS namespace { int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } } // namespace int main() { int N = read_int(); int M = read_int(); int Q = read_int(); std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q); for (int j = 0; j < M; ++j) { X[j] = read_int(); Y[j] = read_int(); } for (int i = 0; i < Q; ++i) { S[i] = read_int(); E[i] = read_int(); L[i] = read_int(); R[i] = read_int(); } std::vector<int> A = check_validity(N,X,Y,S,E,L,R); for (size_t i = 0; i < A.size(); ++i) { printf("%d\n", A[i]); } return 0; } #endif /* 10 9 10 6 7 1 5 8 0 2 9 9 4 2 7 8 5 6 0 3 4 4 9 0 9 8 1 8 9 1 8 1 8 8 3 5 5 8 9 3 9 0 1 0 2 9 0 6 6 1 7 1 8 9 4 5 6 9 5 0 9 */

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:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0;i<X.size();i++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...