oj.uz

Submission #420170

# Submission time Handle Problem Language Result Execution time Memory
420170 2021-06-08T07:01:51 Z Jasiekstrz Werewolf (IOI18_werewolf) C++17
100 / 100
 1170 ms 103184 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].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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 15 ms 15600 KB Output is correct
11 Correct 14 ms 15568 KB Output is correct
12 Correct 18 ms 15568 KB Output is correct
13 Correct 15 ms 15540 KB Output is correct
14 Correct 14 ms 15564 KB Output is correct
15 Correct 16 ms 15660 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 954 ms 88572 KB Output is correct
2 Correct 635 ms 93184 KB Output is correct
3 Correct 620 ms 92716 KB Output is correct
4 Correct 737 ms 92736 KB Output is correct
5 Correct 724 ms 92924 KB Output is correct
6 Correct 809 ms 93456 KB Output is correct
7 Correct 939 ms 96184 KB Output is correct
8 Correct 598 ms 93284 KB Output is correct
9 Correct 540 ms 92856 KB Output is correct
10 Correct 646 ms 92808 KB Output is correct
11 Correct 605 ms 92836 KB Output is correct
12 Correct 718 ms 94028 KB Output is correct
13 Correct 666 ms 99180 KB Output is correct
14 Correct 665 ms 99084 KB Output is correct
15 Correct 644 ms 99140 KB Output is correct
16 Correct 729 ms 99124 KB Output is correct
17 Correct 983 ms 96188 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 9 ms 14412 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 15 ms 15600 KB Output is correct
11 Correct 14 ms 15568 KB Output is correct
12 Correct 18 ms 15568 KB Output is correct
13 Correct 15 ms 15540 KB Output is correct
14 Correct 14 ms 15564 KB Output is correct
15 Correct 16 ms 15660 KB Output is correct
16 Correct 954 ms 88572 KB Output is correct
17 Correct 635 ms 93184 KB Output is correct
18 Correct 620 ms 92716 KB Output is correct
19 Correct 737 ms 92736 KB Output is correct
20 Correct 724 ms 92924 KB Output is correct
21 Correct 809 ms 93456 KB Output is correct
22 Correct 939 ms 96184 KB Output is correct
23 Correct 598 ms 93284 KB Output is correct
24 Correct 540 ms 92856 KB Output is correct
25 Correct 646 ms 92808 KB Output is correct
26 Correct 605 ms 92836 KB Output is correct
27 Correct 718 ms 94028 KB Output is correct
28 Correct 666 ms 99180 KB Output is correct
29 Correct 665 ms 99084 KB Output is correct
30 Correct 644 ms 99140 KB Output is correct
31 Correct 729 ms 99124 KB Output is correct
32 Correct 983 ms 96188 KB Output is correct
33 Correct 843 ms 93864 KB Output is correct
34 Correct 417 ms 50380 KB Output is correct
35 Correct 1043 ms 95076 KB Output is correct
36 Correct 1035 ms 93468 KB Output is correct
37 Correct 941 ms 94624 KB Output is correct
38 Correct 1042 ms 93644 KB Output is correct
39 Correct 925 ms 93188 KB Output is correct
40 Correct 1170 ms 101816 KB Output is correct
41 Correct 902 ms 94292 KB Output is correct
42 Correct 904 ms 93668 KB Output is correct
43 Correct 1056 ms 97380 KB Output is correct
44 Correct 939 ms 94668 KB Output is correct
45 Correct 769 ms 93680 KB Output is correct
46 Correct 729 ms 93196 KB Output is correct
47 Correct 757 ms 99272 KB Output is correct
48 Correct 706 ms 99120 KB Output is correct
49 Correct 718 ms 99268 KB Output is correct
50 Correct 721 ms 99132 KB Output is correct
51 Correct 1002 ms 103084 KB Output is correct
52 Correct 1066 ms 103184 KB Output is correct