Submission #771898

#	Time	Username	Problem	Language	Result	Execution time	Memory
771898		alvingogo	Werewolf (IOI18_werewolf)	C++14	100 / 100	588 ms	101504 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1);
	}
	void update(int x,int y){
		for(;x<=n;x+=(x&-x)){
			bt[x]+=y;
		}
	}
	int query(int x){
		int ans=0;
		for(;x>0;x-=(x&-x)){
			ans+=bt[x];
		}
		return ans;
	}
	int sum(int l,int r){
		return query(r)-query(l-1);
	}
};
struct T1{
	struct no{
		vector<int> ch;
		int in,out;
	};
	vector<no> v;
	BIT bt;
	int cnt=0;
	void init(int x){
		v.resize(x);
		bt.init(x+1);
	}
	void add(int x,int y){
		v[x].ch.push_back(y);
		v[y].ch.push_back(x);
	}
	void dfs(int r,int f){
		cnt++;
		v[r].in=cnt;
		for(auto h:v[r].ch){
			if(h!=f){
				dfs(h,r);
			}
		}
		v[r].out=cnt;
	}
	vector<int> s;
	void ap(int r){
		s.push_back(r);
		bt.update(v[r].in,1);
	}
	int query(int r){
		return bt.sum(v[r].in,v[r].out);
	}
	void undo(){
		while(s.size()){
			bt.update(v[s.back()].in,-1);
			s.pop_back();
		}
	}	
}t1;

vector<int> ans;
struct T2{
	struct no{
		vector<int> ch;
		int sz=1;
		int vis=0;
		int mx=-1;
		vector<pair<int,int> > qu;
	};
	vector<no> v;
	void init(int x){
		v.resize(x);
	}
	void add(int x,int y){
		v[x].ch.push_back(y);
		v[y].ch.push_back(x);
	}
	void aq(int r,pair<int,int> a){
		v[r].qu.push_back(a);
	}
	void cal(int r,int f,int t){
		if(!v[r].vis){
			for(auto h:v[r].ch){
				if(h!=f && h!=v[r].mx){
					cal(h,r,1);
				}
			}
		}
		if(v[r].mx>=0){
			cal(v[r].mx,r,0);
		}
		t1.ap(r);
		for(auto h:v[r].ch){
			if(h!=f && h!=v[r].mx){
				cal(h,r,0);
			}
		}
		if(!v[r].vis){
			for(auto h:v[r].qu){
				ans[h.fs]=t1.query(h.sc)>0;
			}
			v[r].vis=1;
		}
		if(t){
			t1.undo();
		}
	}
	void dfs(int r,int f){
		for(auto h:v[r].ch){
			if(h!=f){
				dfs(h,r);
				v[r].sz+=v[h].sz;
				if(v[r].mx==-1 || v[h].sz>v[v[r].mx].sz){
					v[r].mx=h;
				}
			}
		}
		
	}
}t2;

struct DSU{
	vector<int> bo;
	void init(int x){
		bo.resize(x);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	pair<int,int> merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y){
			return {-1,-1};
		}
		bo[y]=x;
		return {x,y};
	}
};
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();
	int m=x.size();
	vector<vector<int> > ls(n),re(n);
	for(int i=0;i<q;i++){
		ls[l[i]].push_back(i);
	}
	for(int i=0;i<q;i++){
		re[r[i]].push_back(i);
	}
	ans.resize(q);
	vector<vector<int> > f(n);
	for(int i=0;i<m;i++){
		f[x[i]].push_back(y[i]);
		f[y[i]].push_back(x[i]);
	}
	t1.init(n);
	DSU d1;
	d1.init(n);
	for(int i=0;i<n;i++){
		for(auto z:f[i]){
			if(z<i){
				auto a=d1.merge(i,z);
				if(a.fs>=0){
					t1.add(a.fs,a.sc);
				}
			}
		}
		for(auto h:re[i]){
			e[h]=d1.find(e[h]);
		}
	}
	t1.dfs(n-1,n-1);
	t2.init(n);
	DSU d2;
	d2.init(n);
	for(int i=n-1;i>=0;i--){
		for(auto z:f[i]){
			if(z>i){
				auto a=d2.merge(i,z);
				if(a.fs>=0){
					t2.add(a.fs,a.sc);
				}
			}
		}
		for(auto h:ls[i]){
			s[h]=d2.find(s[h]);
			t2.aq(s[h],{h,e[h]});
		}
	}
	t2.dfs(0,0);
	t2.cal(0,0,0);
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51