Submission #1280123

#TimeUsernameProblemLanguageResultExecution timeMemory
1280123MMihalevWerewolf (IOI18_werewolf)C++20
15 / 100
2215 ms589824 KiB
#include<iostream> #include<vector> #include<tuple> #include<cmath> #include "werewolf.h" using namespace std; const int MAX_N=2e5+5; const int MAX_M=4e5+5; int BLOCK_SIZE=1500; int n,m,q; vector<int>g[MAX_N]; int l[MAX_N]; int r[MAX_N]; int s[MAX_N]; int e[MAX_N]; vector<int>forleft[MAX_N],forright[MAX_N]; vector<pair<int,int>>checkone[MAX_N]; int pare[MAX_N]; ///init vector<pair<int,int>>updates[MAX_N]; int prevblockcnt[MAX_N]; vector<int>blockqueries[10000000]; ///blocks int parent[MAX_N],sz[MAX_N]; int curtime; int Find(int u) { if(parent[u]==u)return u; return parent[u]=Find(parent[u]); } void Merge(int u,int v,bool f) { int urt=Find(u),vrt=Find(v); if(urt==vrt)return; if(sz[urt]>sz[vrt])swap(urt,vrt); parent[urt]=vrt; sz[vrt]+=sz[urt]; if(!f)return; for(auto [node,useless]:updates[urt]) { updates[vrt].push_back({node,curtime}); } } ///dsu void Update(int query) { int node=pare[query]; int posr,br; int ll=0,rr=updates[node].size()-1; while(ll<=rr) { int mid=(ll+rr)/2; if(updates[node][mid].second<=r[query]) { posr=mid; ll=mid+1; } else rr=mid-1; } br=posr/BLOCK_SIZE; for(int b=0;b<br;b++) { blockqueries[prevblockcnt[node]+b+1].push_back(query); } for(int i=br*BLOCK_SIZE;i<=posr;i++) { checkone[l[query]].push_back({updates[node][i].first,query}); } } vector<int>nodes; vector<int>ans; bool active[MAX_N]; bool used[MAX_N]; void dfs(int u) { used[u]=1; for(int v:g[u]) { if(v>=curtime && !used[v])dfs(v); } } void bfs(int block) { int idxqueries=0; for(int i=0;i<n;i++)used[i]=0; for(int i=n-1;i>=0;i--) { if(active[i])used[i]=1; for(int v:g[i]) { if(v>i) { if(used[v]==used[i])continue; curtime=i; if(used[i])dfs(v); else dfs(i); } } while(idxqueries<blockqueries[block].size() && i==l[blockqueries[block][idxqueries]]) { if(used[s[blockqueries[block][idxqueries]]]) { ans[blockqueries[block][idxqueries]]=1; } idxqueries++; } if(idxqueries>=blockqueries[block].size())break; } for(int u:nodes)active[u]=0; nodes.clear(); } void solve() { for(int i=0;i<n;i++) { parent[i]=i; sz[i]=i; } updates[0].push_back({0,0}); for(int i=1;i<n;i++) { curtime=i; updates[i].push_back({i,i}); for(int v:g[i]) { if(v<i) { Merge(v,i,1); } } for(int query:forright[i]) { pare[query]=Find(e[query]); } } int sum=0; for(int i=0;i<n;i++)sum+=updates[i].size(); //BLOCK_SIZE=(int)(sqrt(sum)); int curblockcnt=0; for(int i=0;i<=n;i++) { prevblockcnt[i]=curblockcnt; curblockcnt+=updates[i].size()/BLOCK_SIZE; } for(int i=n-1;i>=0;i--) { for(int query:forleft[i])Update(query); } ///make queries int block=1; for(int i=0;i<n;i++) { int posl=0,posr=BLOCK_SIZE-1; while(posr<updates[i].size()) { if(blockqueries[block].size()>0) { for(int j=posl;j<=posr;j++) { nodes.push_back(updates[i][j].first); active[updates[i][j].first]=1; } bfs(block); } block++; posl+=BLOCK_SIZE; posr+=BLOCK_SIZE; } } //block queries for(int i=0;i<n;i++) { parent[i]=i; sz[i]=i; } for(int i=n-1;i>=0;i--) { for(int v:g[i]) { if(v>i) { Merge(v,i,0); } } for(auto [u,query]:checkone[i]) { if(Find(u)==Find(s[query]))ans[query]=1; } } //single node queries ///solve queries } 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) { n=N; m=X.size(); for(int i=0;i<m;i++) { int u=X[i],v=Y[i]; g[u].push_back(v); g[v].push_back(u); } q=S.size(); ans.resize(q); for(int i=0;i<q;i++) { s[i]=S[i];e[i]=E[i];l[i]=L[i];r[i]=R[i]; forleft[L[i]].push_back(i); forright[R[i]].push_back(i); } solve(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...