제출 #420170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420170		Jasiekstrz	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1170 ms	103184 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
#define fi first
#define se second
using namespace std;
const int NN=2e5;
struct Que
{
	int l,r,s,e,id;
};
struct Node
{
	bool vis=false;
	int l,r;
	int id;
	vector<Node*> e;
	Node* par;
	Node(int _id) : id(_id)
	{
		par=nullptr;
	}
	Node* f()
	{
		if(par==nullptr)
			return this;
		par=(par->f());
		return par;
	}
	void add_e(Node* x)
	{
		if(x==this)
			return;
		e.push_back(x);
		x->par=this;
		return;
	}
	int dfs(int nr)
	{
		if(vis)
			return nr;
		vis=true;
		if(l==-1)
		{
			l=r=++nr;
			//cerr<<id<<" "<<l<<"\n";
			return nr;
		}
		l=nr+1;
		for(auto v:e)
			nr=v->dfs(nr);
		r=nr;
		return nr;
	}
};
vector<int> e[NN+10];
Que qq[NN+10];
Node* nd[2*NN+10];
Node* tmpq[NN+10];
set<int> st[NN+10];
int fau[NN+10];
pair<int,int> in[NN+10];
vector<int> ans;
bool comp_l(Que a,Que b)
{
	return a.l<b.l;
}
bool comp_r(Que a,Que b)
{
	return a.r<b.r;
}
int f(int x)
{
	if(fau[x]!=x)
		fau[x]=f(fau[x]);
	return fau[x];
}
void u(int x,int y)
{
	x=f(x);
	y=f(y);
	if(x==y)
		return;
	if(st[x].size()<st[y].size())
		swap(x,y);
	for(auto v:st[y])
		st[x].insert(v);
	{set<int> ().swap(st[y]);}
	fau[y]=x;
	return;
}
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 n=N;
	ans.resize(q);
	for(size_t i=0;i<X.size();i++)
	{
		e[X[i]].push_back(Y[i]);
		e[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<q;i++)
		qq[i]={L[i],R[i],S[i],E[i],i};
	sort(qq,qq+q,comp_l);
	for(int i=0;i<n;i++)
		nd[i]=new Node(i);
	for(int i=n-1,j=q-1;i>=0;i--)
	{
		nd[n+(n-1-i)]=new Node(n+(n-1-i));
		auto x=nd[n+(n-1-i)];
		x->add_e(nd[i]->f());
		for(auto v:e[i])
		{
			if(v>=i)
				x->add_e(nd[v]->f());
		}
		while(j>=0 && qq[j].l==i)
		{
			tmpq[j]=(nd[qq[j].s]->f());
			j--;
		}
	}
	for(int i=0;i<n;i++)
		(nd[i]->l)=(nd[i]->r)=-1;
	for(int i=n;i<2*n;i++)
		(nd[i]->l)=(nd[i]->r)=0;
	for(int i=0,lst=-1;i<n;i++)
		lst=(nd[i]->f())->dfs(lst);
	for(int i=0;i<q;i++)
	{
		in[qq[i].id]={tmpq[i]->l,tmpq[i]->r};
		//cerr<<qq[i].id<<" "<<in[qq[i].id].fi<<" "<<in[qq[i].id].se<<"\n";
	}
	sort(qq,qq+q,comp_r);
	for(int i=0;i<n;i++)
	{
		fau[i]=i;
		st[i]={nd[i]->l};
	}
	for(int i=0,j=0;i<n;i++)
	{
		for(auto v:e[i])
		{
			if(v<i)
				u(v,i);
		}
		while(j<q && qq[j].r==i)
		{
			int x=f(qq[j].e);
			auto it=st[x].lower_bound(in[qq[j].id].fi);
			ans[qq[j].id]=(it!=st[x].end() && *it<=in[qq[j].id].se);
			j++;
		}
	}
	return ans;
}

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