Submission #157939

#	Time	Username	Problem	Language	Result	Execution time	Memory
157939		kig9981	Werewolf (IOI18_werewolf)	C++17	100 / 100	828 ms	65272 KiB

werewolf

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

using namespace std;

vector<int> adj[200000], V[200000];
pair<int,int> x[200000], y[200000];
int numx[200000], num_rev[200000], numy[200000], color[200000], tree[200001];

int find_(int a)
{
	return color[a]=a==color[a] ? a:find_(color[a]);
}

void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	if(V[a].size()<V[b].size()) swap(a,b);
	color[b]=a;
	for(auto v: V[b]) V[a].push_back(v);
	V[b].clear();
}

void update(int n, int v)
{
	for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}

int get_cnt(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}

int get_cnt(pair<int,int> S)
{
	return get_cnt(S.second)-get_cnt(S.first-1);
}

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 M=X.size(), Q=S.size(), j=N-1, k;
	vector<tuple<int,int,int>> temp(Q);
	vector<int> ret(Q);
	for(int i=0;i<M;i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<Q;i++) temp[i]=make_tuple(L[i],S[i],i);
	sort(temp.rbegin(),temp.rend());
	for(int i=0;i<N;i++) {
		V[i].resize(1);
		color[V[i][0]=i]=i;
	}
	for(int i=0;i<Q;i++) {
		int l, s, idx;
		tie(l,s,idx)=temp[i];
		for(;j>=l;j--) for(auto n: adj[j]) if(n>j && find_(j)!=find_(n)) union_(j,n);
		s=find_(s);
		x[idx]={V[s].front(),V[s].back()};
	}
	for(;j>=0;j--) for(auto n: adj[j]) if(n>j && find_(j)!=find_(n)) union_(j,n);
	j=find_(0);
	for(int i=0;i<N;i++) numx[num_rev[i]=V[j][i]]=i;
	for(int i=0;i<Q;i++) temp[i]=make_tuple(R[i],E[i],i);
	sort(temp.begin(),temp.end());
	for(int i=0;i<N;i++) {
		V[i].resize(1);
		color[V[i][0]=i]=i;
	}
	for(int i=j=0;i<Q;i++) {
		int r, e, idx;
		tie(r,e,idx)=temp[i];
		for(;j<=r;j++) for(auto n: adj[j]) if(n<j && find_(j)!=find_(n)) union_(j,n);
		e=find_(e);
		y[idx]={V[e].front(),V[e].back()};
	}
	for(;j<N;j++) for(auto n: adj[j]) if(n<j && find_(j)!=find_(n)) union_(j,n);
	j=find_(0);
	for(int i=0;i<N;i++) numy[V[j][i]]=i;
	for(int i=0;i<Q;i++) {
		L[i]=R[i]=i;
		x[i].first=numx[x[i].first];
		x[i].second=numx[x[i].second];
		y[i].first=numy[y[i].first];
		y[i].second=numy[y[i].second];
	}
	sort(L.begin(),L.end(),[&](int a, int b) {return x[a].first<x[b].first;});
	sort(R.begin(),R.end(),[&](int a, int b) {return x[a].second<x[b].second;});
	for(int i=j=k=0;i<N;i++) {
		for(;j<Q && x[L[j]].first==i;j++) ret[L[j]]-=get_cnt(y[L[j]]);
		update(numy[num_rev[i]],1);
		for(;k<Q && x[R[k]].second==i;k++) ret[R[k]]+=get_cnt(y[R[k]]);
	}
	for(int i=0;i<Q;i++) ret[i]=ret[i]>0;
	return ret;
}

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