Submission #608467

#TimeUsernameProblemLanguageResultExecution timeMemory
608467rrrr10000Werewolf (IOI18_werewolf)C++14
0 / 100
909 ms147628 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<P> vp; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++) #define all(a) a.begin(),a.end() #define pb emplace_back #define fi first #define se second template<class T> void out(T a){cout<<a<<endl;} template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;} template<class T> void outvv(T v){for(auto x:v)outv(x);} template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;} const ll inf=1001001001001001001; vector<int> check_validity(int n, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) { int Q = S.size(); vvi g(n); rep(i,X.size()){ g[X[i]].pb(Y[i]);g[Y[i]].pb(X[i]); } vi parL(n,-1),parR(n,-1); vvi queryL(n),queryR(n); { vi pp(n,-1); function<ll(ll)> root=[&](ll i){ if(pp[i]==-1)return i; pp[i]=root(pp[i]); return pp[i]; }; vvi tmp(n); rep(i,Q)tmp[L[i]].pb(i); for(int i=n-1;i>=0;i--){ for(auto x:g[i])if(x>i){ ll t=root(x); if(t!=i)parL[t]=pp[t]=i; } for(ll x:tmp[i])queryL[root(S[x])].pb(x); } } { vi pp(n,-1); function<ll(ll)> root=[&](ll i){ if(pp[i]==-1)return i; pp[i]=root(pp[i]); return pp[i]; }; vvi tmp(n); rep(i,Q)tmp[R[i]].pb(i); rep(i,n){ for(auto x:g[i])if(x<i){ ll t=root(x); if(t!=i)parR[t]=pp[t]=i; } for(ll x:tmp[i])queryR[root(E[x])].pb(x); } } vvi gL(n),gR(n); rep(i,n)if(parL[i]!=-1)gL[parL[i]].pb(i); rep(i,n)if(parR[i]!=-1)gR[parR[i]].pb(i); ll cnt=0; vp euler(n); function<void(ll)> dfs0=[&](ll i){ euler[i].fi=cnt++; for(ll x:gR[i])dfs0(x); euler[i].se=cnt; };dfs0(n-1); vp rng(Q); rep(i,n)for(auto x:queryR[i])rng[x]=euler[i]; vector<set<ll>> dp(n); vector<int> ans(Q); // for(auto x:rng)cout<<x.fi<<' '<<x.se<<endl; // for(auto x:euler)cout<<x.fi<<' '<<x.se<<endl; function<void(ll)> dfs1=[&](ll i){ dp[i].insert(euler[i].fi); for(ll x:gL[i]){ dfs1(x); if(dp[i].size()<dp[x].size())swap(dp[i],dp[x]); for(ll y:dp[x])dp[i].insert(y); } for(auto x:queryL[i]){ auto itr=dp[i].lower_bound(rng[x].fi); if(itr!=dp[i].end()&&*itr<=rng[x].se)ans[x]=1; } };dfs1(0); 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...