oj.uz

답안 #420147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420147 2021-06-08T06:44:58 Z Jasiekstrz 늑대인간 (IOI18_werewolf) C++17
0 / 100
 949 ms 90976 KB 
#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].r);
			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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 949 ms 90976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 14412 KB Output isn't correct
2 Halted 0 ms 0 KB -