Submission #1177449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177449		mertbbm	Werewolf (IOI18_werewolf)	C++20	100 / 100	1159 ms	182184 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<int>krt[400005]; //werewolf
vector<int>krt2[400005]; //human
int val[400005];
int val2[400005];
int ptr=0;

struct DSU{
	vector<int>e;
	vector<int>node;
	void init(int n){
		e=vector<int>(n,-1);
		for(int x=0;x<n;x++){
			node.push_back(x);
		}
	}
	
	int get(int x){
		return e[x]<0?x:get(e[x]);
	}
	
	bool unite(int index, int x, int y){
		int a=x;
		x=get(x); y=get(y);
		if(x==y) return 1;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		if(index==1){
			//show2(ptr,ptr,node[y],node[y]);
			//show2(ptr,ptr,node[x],node[x]);
			krt[ptr].push_back(node[y]);
			krt[ptr].push_back(node[x]);
			val[ptr]=a;
		}
		else{
			krt2[ptr].push_back(node[x]);
			krt2[ptr].push_back(node[y]);
			val2[ptr]=a;
		}
		e[y]=x;
		node[x]=ptr;
		ptr++;
		return 0;
	}
};

vector<int>adj[200005];

int in[400005];
int out[400005];
int two[22][400005];
int tour=0;

void dfs(int index, int par){
	in[index]=++tour;
	for(int x=0;x<20;x++){
		if(two[x][index]==-1) continue;
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:krt[index]){
		if(it==par) continue;
		two[0][it]=index;
		dfs(it,index);
	}
	out[index]=tour;
}

int in2[400005];
int out2[400005];
int two2[22][400005];

void dfs2(int index, int par){
	//show(visited,index);
	in2[index]=++tour;
	for(int x=0;x<20;x++){
		if(two2[x][index]==-1) continue;
		two2[x+1][index]=two2[x][two2[x][index]];
	}
	for(auto it:krt2[index]){
		if(it==par) continue;
		two2[0][it]=index;
		dfs2(it,index);
	}
	out2[index]=tour;
}

//fenwick
int fw[400005];

void upd(int x, int y){
	while(x<400005){
		fw[x]+=y;
		x+=x&(-x);
	}
}

int sum(int x){
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}
	return counter;
}

int query(int x, int y){
	int a=sum(y)-sum(x-1);
	return a;
}

vector<int>storage[400005];
vector<array<int,4>>que[400005]; //l r sgn index

vector<int>check_validity(int n, vector<int>a, vector<int>b, vector<int>s, vector<int>e, vector<int>l, vector<int>r){
	int q=s.size();
	vector<int>ans(q,0);
	
	for(int x=0;x<a.size();x++){
		//show2(a[x],a[x],b[x],b[x]);
		adj[a[x]].push_back(b[x]);
		adj[b[x]].push_back(a[x]);
	}
	
	bool visited[n+5];
	memset(visited,0,sizeof(visited));
	DSU dsu;
	dsu.init(n+5);
	ptr=n;
	for(int x=0;x<n;x++){
		for(auto it:adj[x]){
			if(it<x){
				//show2(x,x,it,it);
				dsu.unite(1,x,it);
			}
		}
	}
	
	memset(two,-1,sizeof(two));
	memset(two2,-1,sizeof(two2));
	
	tour=0;
	dfs(ptr-1,-1);

	DSU dsu2;
	dsu2.init(n+5);
	ptr=n;
	for(int x=n-1;x>=0;x--){
		for(auto it:adj[x]){
			if(it>x){
				dsu2.unite(2,x,it);
			}
		}
	}
	
	tour=0;
	dfs2(ptr-1,-1);
	
	//for(int x=0;x<ptr;x++){
		//show2(x,x,in[x],in[x]);
	//}
	
	for(int x=0;x<q;x++){
		//break down to euler tour
		
		//werewolf
		int cur=e[x];
	
		for(int y=19;y>=0;y--){
			if(two[y][cur]==-1) continue;
			if(val[two[y][cur]]<=r[x]){
				cur=two[y][cur];
			}
		}
		
		pii range={in[cur],out[cur]};
		
		//human
		cur=s[x];
		for(int y=19;y>=0;y--){
			if(two2[y][cur]==-1) continue;
			if(val2[two2[y][cur]]>=l[x]){
				cur=two2[y][cur];
			}
		}
		pii range2={in2[cur],out2[cur]};
		
		que[range2.first-1].push_back({range.first,range.second,-1,x});
		que[range2.second].push_back({range.first,range.second,1,x});
	}
	
	for(int x=0;x<n;x++){
		//show2(in[x],in[x],in2[x],in2[x]);
		storage[in2[x]].push_back(in[x]);
	}	
	
	for(int x=0;x<=2*n;x++){
		//show(x,x);
		for(auto it:storage[x]){
			//show(it,it);
			upd(it,1);
		}
		
		for(auto it:que[x]){
			//cout << it[0] << " " << it[1] << " " << it[2] << " " << it[3] << endl;
			ans[it[3]]+=query(it[0],it[1])*it[2];
		}
	}	
	
	for(int x=0;x<q;x++){
		ans[x]=min(ans[x],1);
	}
	
	return ans;
}

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