Submission #1208609

#TimeUsernameProblemLanguageResultExecution timeMemory
1208609loiiii12358Werewolf (IOI18_werewolf)C++20
49 / 100
4091 ms347180 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; struct SegTree2D{ vector<bool> cnt={false}; vector<vector<int>> child={{}}; void add(int id,int lx,int ly,int rx,int ry,int &x,int &y){ if(x<lx||x>rx||y<ly||y>ry){ return; }else if(lx==rx&&ly==ry){ cnt[id]=true; return; } int mx=lx+(rx-lx)/2,my=ly+(ry-ly)/2; if(child[id].size()==0){ int tmp=child.size(); for(int i=0;i<4;i++){ child[id].push_back(tmp+i); child.push_back({}); cnt.push_back(false); } } add(child[id][0],lx,ly,mx,my,x,y); add(child[id][1],mx+1,ly,rx,my,x,y); add(child[id][2],lx,my+1,mx,ry,x,y); add(child[id][3],mx+1,my+1,rx,ry,x,y); for(int i=0;i<4;i++){ cnt[id]=cnt[id]||cnt[child[id][i]]; } } bool query(int id,int lx,int ly,int rx,int ry,int &Lx,int &Ly,int &Rx,int &Ry){ // cout << id << ' ' << lx << ' ' << ly << ' ' << rx << ' ' << ry << ' ' << cnt[id] << '\n'; if(Rx<lx||Lx>rx||Ry<ly||Ly>ry){ return false; }else if(lx>=Lx&&rx<=Rx&&ly>=Ly&&ry<=Ry){ return cnt[id]; }else if(!cnt[id]){ return cnt[id]; } bool ans=false; int mx=lx+(rx-lx)/2,my=ly+(ry-ly)/2; ans=ans||query(child[id][0],lx,ly,mx,my,Lx,Ly,Rx,Ry); ans=ans||query(child[id][1],mx+1,ly,rx,my,Lx,Ly,Rx,Ry); ans=ans||query(child[id][2],lx,my+1,mx,ry,Lx,Ly,Rx,Ry); ans=ans||query(child[id][3],mx+1,my+1,rx,ry,Lx,Ly,Rx,Ry); return ans; } }; int n; vector<int> node_wolf,dsu,order_wolf,node_human,order_human; vector<vector<int>> par_wolf,par_human; vector<pair<int,int>> edge,child_wolf,bound_wolf,child_human,bound_human; int find_root(int &u){ if(u==dsu[u]){ return u; } return dsu[u]=find_root(dsu[u]); } void dfs_wolf(int u){ for(int i=1;i<18;i++){ par_wolf[u][i]=par_wolf[par_wolf[u][i-1]][i-1]; } if(u<n){ order_wolf.push_back(u); bound_wolf[u]={order_wolf.size(),order_wolf.size()}; return; } dfs_wolf(child_wolf[u].first); dfs_wolf(child_wolf[u].second); bound_wolf[u]={bound_wolf[child_wolf[u].first].first,bound_wolf[child_wolf[u].second].second}; } void dfs_human(int u){ for(int i=1;i<18;i++){ par_human[u][i]=par_human[par_human[u][i-1]][i-1]; } if(u<n){ order_human.push_back(u); bound_human[u]={order_human.size(),order_human.size()}; return; } dfs_human(child_human[u].first); dfs_human(child_human[u].second); bound_human[u]={bound_human[child_human[u].first].first,bound_human[child_human[u].second].second}; } 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; int Q = S.size(); vector<int> A(Q); edge.resize(X.size()); for(int i=0;i<X.size();i++){ edge[i]={max(X[i],Y[i]),min(X[i],Y[i])}; } sort(edge.begin(),edge.end()); node_wolf.resize(N);par_wolf.resize(N);dsu.resize(N);child_wolf.resize(N); for(int i=0;i<N;i++){ node_wolf[i]=i; par_wolf[i].resize(18,i); dsu[i]=i; } for(int i=0;i<edge.size();i++){ int u=find_root(edge[i].first),v=find_root(edge[i].second); if(u!=v){ par_wolf[u][0]=node_wolf.size(); par_wolf[v][0]=node_wolf.size(); child_wolf.push_back({u,v}); dsu[u]=dsu[v]=node_wolf.size(); node_wolf.push_back(edge[i].first); par_wolf.push_back(vector<int>(18,par_wolf.size())); dsu.push_back(dsu.size()); } } bound_wolf.resize(dsu.size()); dfs_wolf(bound_wolf.size()-1); for(int i=0;i<X.size();i++){ edge[i]={min(X[i],Y[i]),max(X[i],Y[i])}; } sort(edge.begin(),edge.end()); node_human.resize(N);par_human.resize(N);dsu.clear();dsu.resize(N);child_human.resize(N); for(int i=0;i<N;i++){ node_human[i]=i; par_human[i].resize(18,i); dsu[i]=i; } for(int i=edge.size()-1;i>=0;i--){ int u=find_root(edge[i].first),v=find_root(edge[i].second); if(u!=v){ par_human[u][0]=node_human.size(); par_human[v][0]=node_human.size(); child_human.push_back({u,v}); dsu[u]=dsu[v]=node_human.size(); node_human.push_back(edge[i].first); par_human.push_back(vector<int>(18,par_human.size())); dsu.push_back(dsu.size()); } } bound_human.resize(dsu.size()); dfs_human(bound_human.size()-1); SegTree2D ds; vector<pair<int,int>> coor; coor.resize(order_human.size()); for(int i=0;i<order_human.size();i++){ coor[order_human[i]].first=i+1; coor[order_wolf[i]].second=i+1; } for(int i=0;i<order_human.size();i++){ ds.add(0,1,1,N,N,coor[i].first,coor[i].second); } for(int i=0;i<Q;i++){ for(int j=17;j>=0;j--){ if(node_human[par_human[S[i]][j]]>=L[i]){ S[i]=par_human[S[i]][j]; } if(node_wolf[par_wolf[E[i]][j]]<=R[i]){ E[i]=par_wolf[E[i]][j]; } } if(ds.query(0,1,1,N,N,bound_human[S[i]].first,bound_wolf[E[i]].first,bound_human[S[i]].second,bound_wolf[E[i]].second)){ A[i]=1; }else{ A[i]=0; } } return A; } //Nlog(N) //Qlog(N)^2
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...