| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 987397 | yeediot | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#else
#include "werewolf.h"
void setio(){}
#endif
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn=2e5+5;
int n;
vector<int>adj2[mxn];
struct DSU{
vector<int>to(mxn);
void init(){
for(int i=0;i<=n;i++){
to[i]=i;
}
}
int find(int x){
return x==to[x]?x:to[x]=find(to[x]);
}
}d;
struct tree{
vector<vector<int>>adj,jump;
int flg, timer, in[mxn], out[mxn], ord[mxn];
void init(int f){
adj.resize(n+1);
flg=f;
jump.resize(20,vector<int>(n+1));
}
void dfs(int v,int pa){
in[v]=++timer;
ord[timer]=v;
jump[0][v]=pa;
for(auto u:adj[v]){
if(u!=pa)dfs(u,v);
}
out[v]=timer;
}
void build(){
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
jump[i][j]=jump[i-1][jump[i-1][j]];
}
}
}
int find(int st,int x){
if(flg){
for(int i=19;i>=0;i--){
if(jump[i][st]<=x){
st=jump[i][st];
}
}
}
else{
for(int i=19;i>=0;i--){
if(jump[i][st]>=x){
st=jump[i][st];
}
}
}
return st;
}
}mn, mx;
vector<int>upd(mxn),ans;
vector<pair<int,int>>in[mxn];
int bit[mxn];
void modify(int p){
for(;p<=n;p+=p&-p){
bit[p]++;
}
}
int query(int p){
int res=0;
for(;p;p-=p&-p){
res+=bit[p];
}
return res;
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
why_TOI_is_so_de;
n=N;
ans.resize(sz(E));
for(int i=0;i<sz(X);i++){
int a=X[i],b=Y[i];
a++;
b++;
adj2[a].pb(b);
adj2[b].pb(a);
}
mn.init(1);
mx.init(0);
d.init();
for(int x=n;x>=1;x--){
for(auto y:adj2[x]){
if(y<x)continue;
int fx=d.find(y),fy=d.find(x);
if(fx==fy)continue;
mx.adj[fy].pb(fx);
d.to[fx]=fy;
}
}
d.init();
for(int x=1;x<=n;x++){
for(auto y:adj2[x]){
if(y>x)continue;
int fx=d.find(y),fy=d.find(x);
if(fx==fy)continue;
mn.adj[fy].pb(fx);
d.to[fx]=fy;
}
}
mn.dfs(n,n);
mx.dfs(1,1);
mn.build();
mx.build();
for(int i=1;i<=n;i++){
upd[i]=mn.in[mx.ord[i]];
}
for(int i=0;i<sz(S);i++){
int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
int fs=mx.find(s,l),se=mn.find(e,r);
S[i]=se;
in[mx.in[fs]-1].pb({i,-1});
in[mx.out[fs]].pb({i,1});
}
for(int i=1;i<=n;i++){
modify(upd[i]);
for(auto [id,flg]:in[i]){
ans[id]+=flg*(query(mn.out[S[id]])-query(mn.in[S[id]]-1));
if(flg==1 and ans[id])ans[id]=1;
}
}
return ans;
}
/*
input:
[fx,fy] = [2, 3]
[fx,fy] = [3, 4]
[fx,fy] = [1, 4]
[fx,fy] = [4, 5]
[fx,fy] = [5, 6]
[fx,fy] = [5, 4]
[fx,fy] = [6, 3]
[fx,fy] = [3, 2]
[fx,fy] = [4, 2]
[fx,fy] = [2, 1]
*/