Submission #132303

#	Time	Username	Problem	Language	Result	Execution time	Memory
132303		figter001	Werewolf (IOI18_werewolf)	C++17	0 / 100	4018 ms	98908 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int nax = 2e5+50;

int dsu[nax];
int sz_sg[nax],p_sg[nax][20],fr_sg[nax],to_sg[nax],val_sg[nax],nxt_sg[nax],seg_sg[nax],d_sg[nax];
int sz_bg[nax],p_bg[nax][20],fr_bg[nax],to_bg[nax],val_bg[nax],nxt_bg[nax],seg_bg[nax],d_bg[nax];
int n,m,T = 1;
vector<int> sg[nax],bg[nax];

// DSU
int find(int u){
	return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}

// HLD SMALL Graph
void dfs_sz_sg(int u,int p){
	sz_sg[u] = 1;
    for(auto &v: sg[u]) {
    	if(v == p)continue;
    	d_sg[v] = d_sg[u] + 1;
    	p_sg[v][0] = u;
    	for(int i=1;i<20;i++)p_sg[v][i] = p_sg[p_sg[v][i-1]][i-1];
        dfs_sz_sg(v,u);
        sz_sg[u] += sz_sg[v];
        if(sz_sg[v] > sz_sg[sg[u][0]]) {
            swap(v, sg[u][0]);
        }
    }
}

void dfs_hld_sg(int u,int par) {
    fr_sg[u] = T++;
    val_sg[fr_sg[u]] = u;
    for(auto v: sg[u]) {
    	if(v == par)continue;
        nxt_sg[v] = (v == sg[u][0] ? nxt_sg[u] : v);
        dfs_hld_sg(v,u);
    }
    to_sg[u] = T;
}

void hld_sg(){
	T=1;
	dfs_sz_sg(1,0);
	dfs_hld_sg(1,0);
}

// HLD BIG Graph
void dfs_sz_bg(int u,int p){
	sz_bg[u] = 1;
    for(auto &v: bg[u]) {
    	if(v == p)continue;
    	d_bg[v] = d_bg[u] + 1;
    	p_bg[v][0] = u;
    	for(int i=1;i<20;i++)p_bg[v][i] = p_bg[p_bg[v][i-1]][i-1];
        dfs_sz_bg(v,u);
        sz_bg[u] += sz_bg[v];
        if(sz_bg[v] > sz_bg[bg[u][0]]) {
            swap(v, bg[u][0]);
        }
    }
}

void dfs_hld_bg(int u,int par) {
    fr_bg[u] = T++;
    val_bg[fr_bg[u]] = u;
    for(auto v: bg[u]) {
    	if(v == par)continue;
        nxt_bg[v] = (v == bg[u][0] ? nxt_bg[u] : v);
        dfs_hld_bg(v,u);
    }
    to_bg[u] = T;
}

void hld_bg(){
	T=1;
	dfs_sz_bg(n,0);
	dfs_hld_bg(n,0);
}

// SMALL Tree Segment tree
void build_sg(int n,int s,int e){
	if(s == e){
		seg_sg[n] = val_sg[s];
		return;
	}
	build_sg(n*2,s,(s+e)/2);
	build_sg(n*2+1,(s+e)/2+1,e);
	seg_sg[n] = max( seg_sg[n*2] , seg_sg[n*2+1] );
}

int get_sg(int n,int s,int e,int l,int r){
	if(s > r || e < l)return 0;
	if(s >= l && e <= r)return seg_sg[n];
	return max( get_sg(n*2,s,(s+e)/2,l,r) , get_sg(n*2+1,(s+e)/2+1,e,l,r) );
}

// BIG Tree Segment tree
void build_bg(int n,int s,int e){
	if(s == e){
		seg_bg[n] = val_bg[s];
		return;
	}
	build_bg(n*2,s,(s+e)/2);
	build_bg(n*2+1,(s+e)/2+1,e);
	seg_bg[n] = min( seg_bg[n*2] , seg_bg[n*2+1] );
}

int get_bg(int n,int s,int e,int l,int r){
	if(s > r || e < l)return 1e9;
	if(s >= l && e <= r)return seg_bg[n];
	return min( get_bg(n*2,s,(s+e)/2,l,r) , get_bg(n*2+1,(s+e)/2+1,e,l,r) );
}

// SMALL TREE LCA
int kth_sg(int u,int dif){
	for(int k = 19;k>=0;k--){
		if( (dif >> k) & 1 ){
			u = p_sg[u][k];
		}
	}
	return u;
}

int lca_sg(int u,int v){
	if(d_sg[u] < d_sg[v])swap(u,v);
	int dif = d_sg[u] - d_sg[v];
	assert(dif >= 0);
	u = kth_sg(u,dif);
	if(u == v)return u;
	for(int k=19;k>=0;k--){
		if(p_sg[u][k] != p_sg[v][k]){
			u = p_sg[u][k];
			v = p_sg[v][k];
		}
	}
	assert(u!=v);
	return p_sg[u][0];
}

// BIG Tree LCA
int kth_bg(int u,int dif){
	for(int k = 19;k>=0;k--){
		if( (dif >> k) & 1 ){
			u = p_bg[u][k];
		}
	}
	return u;
}

int lca_bg(int u,int v){
	if(d_bg[u] < d_bg[v])swap(u,v);
	int dif = d_bg[u] - d_bg[v];
	assert(dif >= 0);
	u = kth_bg(u,dif);
	if(u == v)return u;
	for(int k=19;k>=0;k--){
		if(p_bg[u][k] != p_bg[v][k]){
			u = p_bg[u][k];
			v = p_bg[v][k];
		}
	}
	assert(u!=v);
	return p_bg[u][0];
}

// Answring Queries
int find_smallest(int u,int v,int l,int r){
	int small = -1;
	int w = lca_bg(u,v);
	assert(w);
	bool done = 0;
	int tmp,lo,hi,md;
	for(int x = u;!done;x=p_bg[nxt_bg[x]][0]){
		if(d_bg[nxt_bg[x]] <= d_bg[w]){
			tmp = get_bg(1,1,n,fr_bg[w],fr_bg[x]);
			lo = fr_bg[w];hi = fr_bg[x];
			done = 1;
		}else{
			tmp = get_bg(1,1,n,fr_bg[nxt_bg[x]],fr_bg[x]);
			lo = fr_bg[nxt_bg[x]];hi = fr_bg[x];
		}
		if(tmp < l){
			int lim = hi;
			small = lo;
			while(lo <= hi){
				md = (lo + hi)/2;
				int cur = get_bg(1,1,n,md,lim);
				if(cur >= l){
					small = md;
					hi = md-1;
				}else lo = md+1;
			}
			assert(small);
			return small;
		}
	}
	done = 0;
	vector<pair<int,pair<int,int>>> ranges;
	for(int x = v;!done;x=p_bg[nxt_bg[x]][0]){
		if(d_bg[nxt_bg[x]] <= d_bg[w]){
			tmp = get_bg(1,1,n,fr_bg[w],fr_bg[x]);
			lo = fr_bg[w];hi = fr_bg[x];
			done = 1;
		}else{
			tmp = get_bg(1,1,n,fr_bg[nxt_bg[x]],fr_bg[x]);
			lo = fr_bg[nxt_bg[x]];hi = fr_bg[x];
		}
		ranges.push_back({tmp,{lo,hi}});
	}
	reverse(ranges.begin(),ranges.end());
	for(auto cur : ranges){
		lo = cur.second.first;
		hi = cur.second.second;
		int lim = lo;
		int val = cur.first;
		if(val < l){
			small = lo;
			while(lo <= hi){
				md = (lo + hi)/2;
				int cur = get_bg(1,1,n,lim,md);
				if(cur >= l){
					small = md;
					lo = md+1;
				}else hi = md-1;
			}
			assert(small);
			return small;
		}
	}
	return 0;
}

int find_largest(int u,int v,int l,int r){
	int w = lca_sg(u,v);
	int tmp;
	assert(w);
	bool done = 0;
	for(int x = u;!done;x=p_sg[nxt_sg[x]][0]){
		if(d_sg[nxt_sg[x]] <= d_sg[w]){
			tmp = get_sg(1,1,n,fr_sg[w],fr_sg[x]);
			done = 1;
		}else{
			tmp = get_sg(1,1,n,fr_sg[nxt_sg[x]],fr_sg[x]);
		}
		if(tmp > r)return 0;
	}
	done = 0;
	for(int x = v;!done;x=p_sg[nxt_sg[x]][0]){
		if(d_sg[nxt_sg[x]] <= d_sg[w]){
			tmp = get_sg(1,1,n,fr_sg[w],fr_sg[x]);
			done = 1;
		}else{
			tmp = get_sg(1,1,n,fr_sg[nxt_sg[x]],fr_sg[x]);
		}
		if(tmp > r)return 0;
	}
	return 1;
}

int solve(int fr,int to,int l,int r){
	fr = find_smallest(fr,to,l,r);
	if(fr == 0)return 1;
	fr = get_bg(1,1,n,fr,fr);
	if(fr > r || fr < l)return 0;
	return find_largest(fr,to,l,r);
}

vector<int> check_validity(int N, vector<int> x, vector<int> y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	n = N;
	m = x.size();
	int Q = S.size();
	vector<vector<int>> tmp(n+1);

	for(int i=0;i<m;i++){
		int u = x[i];
		int v = y[i];
		u++;v++;
		tmp[u].push_back(v);
		tmp[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		sort(tmp[i].begin(),tmp[i].end());
		dsu[i] = i;
	}

	for(int u=1;u<=n;u++){
		for(int v : tmp[u]){
			if(find(v) == find(u) || u > v)continue;
			sg[u].push_back(v);
			sg[v].push_back(u);
			dsu[find(v)] = find(u);
		}
	}

	for(int i=1;i<=n;i++){
		reverse(tmp[i].begin(),tmp[i].end());
		dsu[i] = i;
	}

	for(int u=n;u>=1;u--){
		for(int v : tmp[u]){
			if(find(v) == find(u) || u < v)continue;
			bg[u].push_back(v);
			bg[v].push_back(u);
			dsu[find(v)] = find(u);
		}
	}

	for(int i=1;i<=n;i++){
		nxt_sg[i] = 1;
		nxt_bg[i] = n;
	}

	hld_sg();
	hld_bg();

	build_sg(1,1,n);
	build_bg(1,1,n);

	vector<int> A(Q,0);
	for (int i = 0; i < Q; ++i) {
		S[i]++;E[i]++;L[i]++;R[i]++;
		A[i] = solve(S[i],E[i],L[i],R[i]);
	}
	return A;
}

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