Submission #727224

#	Time	Username	Problem	Language	Result	Execution time	Memory
727224		myrcella	Werewolf (IOI18_werewolf)	C++17	100 / 100	717 ms	82144 KiB

werewolf

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "werewolf.h"

const int maxn = 4e5+10;

int n;
int st[maxn][20];
vector <pii> edge;
int f[maxn],idx[maxn],node[maxn],lc[maxn],rc[maxn];
int dfn = 0;
pii rg[maxn],qs[maxn];
int w[maxn];

int tree[maxn];

void update(int x) {
	x++;
	while (x<maxn) {
		tree[x]++;
		x += lowbit(x);
	}
	return;
}

int query(int x) {
	x++;
	int ret = 0;
	while (x>0) {
		ret += tree[x];
		x-=lowbit(x);
	}
	return ret;
}

struct QQ{
	int val;
	int ss;
	pii range;
	int id;
} q[maxn];

bool cmpq(QQ x,QQ y) {
	return x.ss<y.ss;
}

int ans[maxn];

bool cmp1(pii x,pii y) {
	return min(x.fi,x.se) > min(y.fi,y.se);
}

bool cmp2(pii x,pii y) {
	return max(x.fi,x.se) < max(y.fi,y.se);
}

int getf(int x) {
	if (f[x]==x) return x;
	return f[x] = getf(f[x]);
}

void dfs(int u) {
	rep(i,1,20) {
		if (st[u][i-1]==-1) break;
		st[u][i] = st[st[u][i-1]][i-1];
	}
	if (u<n) idx[u] = rg[u].fi = rg[u].se = dfn++;
	else {
		dfs(lc[u]),dfs(rc[u]);
		rg[u] = {rg[lc[u]].fi,rg[rc[u]].se};
		assert(rg[lc[u]].se+1==rg[rc[u]].fi);
	}
	
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
	int tot = N;
	memset(st,-1,sizeof(st));
	n = N;
	rep(i,0,SZ(X)) edge.pb({X[i],Y[i]});
	sort(ALL(edge),cmp1);
	rep(i,0,N) f[i] = i;
	for (auto it:edge) {
		int fx = getf(it.fi),fy = getf(it.se);
		if (fx==fy) continue;
		st[fx][0] = st[fy][0] = tot;
		f[tot] = tot;
		w[tot] = min(it.fi,it.se);
		lc[tot] = fx, rc[tot] = fy;
		f[fx] = f[fy] = tot++;
	}
	dfs(tot-1);
	rep(i,0,SZ(S)) {
		int u = S[i];
		for (int j = 19;j>=0;j--) 
			if (st[u][j]!=-1 and w[st[u][j]]>=L[i]) u = st[u][j];
		qs[i] = rg[u];
	}
	rep(i,0,n) node[idx[i]] = i;
	//------
	tot = n;
	memset(st,-1,sizeof(st));
	sort(ALL(edge),cmp2);
	rep(i,0,N) f[i] = i;
	for (auto it:edge) {
		int fx = getf(it.fi),fy = getf(it.se);
		if (fx==fy) continue;
		st[fx][0] = st[fy][0] = tot;
		f[tot] = tot;
		w[tot] = max(it.fi,it.se);
		lc[tot] = fx, rc[tot] = fy;
		f[fx] = f[fy] = tot++;
	}
	dfs(tot-1);
	rep(i,0,SZ(S)) {
		int u = E[i];
		for (int j=19;j>=0;j--)
			if (st[u][j]!=-1 and w[st[u][j]]<=R[i]) u = st[u][j];
		q[i*2].id = q[i*2+1].id = i;
		q[i*2].range = q[i*2+1].range = rg[u];
		q[i*2].ss = qs[i].fi-1, q[i*2+1].ss = qs[i].se;
		q[i*2].val = -1, q[i*2+1].val = 1;
	}
	sort(q,q+SZ(S)*2,cmpq);
	int cur = 0;
	for (auto it:q) {
		while (cur<=it.ss) update(idx[node[cur++]]);
		ans[it.id] += it.val * (query(it.range.se) - query(it.range.fi-1));
	}
	vector <int> ret;
	rep(i,0,SZ(S)) {
		assert(ans[i]>=0);
		ret.pb((ans[i]>0));
	}
	return ret;
}

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