Submission #368799

#TimeUsernameProblemLanguageResultExecution timeMemory
368799kig9981Collapse (JOI18_collapse)C++17
35 / 100
1977 ms524292 KiB
#include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; const int BC=300, SZ=1<<17; vector<int> adj[100000], BB, tree[2*SZ]; vector<tuple<int,int,int>> qry; vector<pair<int,int>> E; map<pair<int,int>,int> idx; int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000]; bool EX[100000]; void add_edge(int s, int e, int v) { for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) { if(s&1) tree[s++].push_back(v); if(~e&1) tree[e--].push_back(v); } } void flip_edge(int c, int i) { if(EX[c]) add_edge(LL[c],i-1,c); else LL[c]=i; EX[c]^=1; } int find_(int a) { while(color[a]!=a) a=color[a]; return a; } void union_(int a, int b) { a=find_(a); b=find_(b); if(a==b) return; if(cnt[a]<cnt[b]) swap(a,b); cnt[color[b]=a]+=cnt[b]; BB.push_back(b); } void restore(int sz) { while(BB.size()>sz) { cnt[color[BB.back()]]-=cnt[BB.back()]; color[BB.back()]=BB.back(); BB.pop_back(); } } void solve(int bit, int s, int e) { int m=(s+e)>>1, bsz=BB.size(); if(qry.size()<=s) return; for(auto v: tree[bit]) union_(E[v].first,E[v].second); if(s==e) { ans[get<2>(qry[m])]=N-BB.size(); restore(bsz); return; } solve(2*bit,s,m); solve(2*bit+1,m+1,e); restore(bsz); } vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) { int C=T.size(), Q=W.size(), w, p; ::N=N; for(int i=0;i<C;i++) { if(X[i]>Y[i]) swap(X[i],Y[i]); if(idx.count({X[i],Y[i]})==0) { idx[{X[i],Y[i]}]=E.size(); E.emplace_back(X[i],Y[i]); } B[i]=idx[{X[i],Y[i]}]; adj[X[i]].push_back(i); adj[Y[i]].push_back(i); } for(int i=0;i<Q;i++) qry.emplace_back(W[i],P[i],i); sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) { if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC; return get<1>(a)<get<1>(b); }); memset(LL,w=p=-1,sizeof(LL)); for(int i=0;i<Q;i++) { auto[cw,cp,j]=qry[i]; while(w<cw) { int c=B[++w]; auto[a,b]=E[c]; if(a<=p && p<b) continue; flip_edge(c,i); } while(w>cw) { int c=B[w--]; auto[a,b]=E[c]; if(a<=p && p<b) continue; flip_edge(c,i); } while(p<cp) { int c=++p; for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i); } while(p>cp) { int c=p--; for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i); } } for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i); for(int i=0;i<N;i++) cnt[color[i]=i]=1; solve(1,0,SZ-1); return vector<int>(ans,ans+Q); }

Compilation message (stderr)

collapse.cpp: In function 'void restore(int)':
collapse.cpp:53:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  while(BB.size()>sz) {
      |        ~~~~~~~~~^~~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:63:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  if(qry.size()<=s) return;
      |     ~~~~~~~~~~^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:118:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,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...