Submission #1159485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159485		Gr1sen	Werewolf (IOI18_werewolf)	C++20	0 / 100	632 ms	281080 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<queue>
#include<unordered_set>
#include<algorithm>
#include<iomanip>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pi pair<ll, ll>
#define us unordered_set<ll>
#define vp vector<pi>
#define vvp vector<vp>

vvi Adj;

void us_print(us& L1) {
	cerr << "{";
	for (auto i : L1) {
		cerr << i << ", ";
	}
	cerr << "}";
}

struct treeNode {
	ll v = -1;
	ll par = -1;
	us US;

	void print() {
		cerr << "treeNode : {";
		cerr << "v : " << v << ", ";
		cerr << "par : " << par << ", ";
		cerr << "US : ";
		us_print(US);
		cerr << "}" << endl;
	}

	void merge(us US2) {
		if (US2.size() > US.size()) swap(US2, US);
		for (auto i : US2) {
			US.insert(i);
		}
	}
};

vector<treeNode> TN1, TN2;

ll find(ll a, vector<treeNode> &TN){
	//cerr << "find " << a << endl;
	return TN[a].par == -1 ? a : TN[a].par = find(TN[a].par, TN);
}

void print(vector<treeNode>& L1) {
	for (auto i : L1) {
		i.print();
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	ll Q = S.size();
	vector<int> A(Q, -1);
	Adj = vvi(N);
	TN1 = vector<treeNode>(N);
	TN2 = vector<treeNode>(N);
	for (ll i = 0; i < X.size(); i++) {
		Adj[X[i]].push_back(Y[i]);
		Adj[Y[i]].push_back(X[i]);
	}

	vp LS(Q), RS(Q);
	for (ll i = 0; i < Q; i++) {
		LS[i] = {L[i], i};
		RS[i] = {R[i], i};
	}
	sort(LS.begin(), LS.end());
	sort(RS.begin(), RS.end());

	ll rsp = 0;
	for (ll i = 0; i < N; i++) {
		//cerr << i << endl;
		TN1[i].v = i;
		for (auto j : Adj[i]) {
			if (j > i) continue;
			if (find(j, TN1) != i) {
				TN1[find(j, TN1)].par = i;
			}
		}
		while (rsp < Q && RS[rsp].first <= i) {
			//cerr << "rsp : " << rsp << endl;
			ll a = RS[rsp].second;
			//cerr << "a : " << a << endl;
			TN1[find(E[a], TN1)].US.insert(a);
			rsp++;
		} 
	}

	//print(TN1);

	ll lsp = Q-1;
	for (ll i = N-1; i > -1; i--) {
		//cerr << "i : " << i << endl;
		TN2[i].v = i;
		TN2[i].US = TN1[i].US;
		for (auto j : Adj[i]) {
			//cerr << "j " << j << endl;
			if (j < i) continue;
			if (find(j, TN2) != i) {
				TN2[i].merge(TN2[find(j, TN2)].US);
				TN2[find(j, TN2)].par = i;
			}
		}
		//cerr << "oink" << endl;
		while (lsp > -1 && LS[lsp].first >= i) {
			ll a = LS[lsp].second;
			ll c = S[a];
			lsp--;
			//cerr << "a : " << a << endl;
			//cerr << "find(c) : " << find(c, TN2) << endl;
			treeNode& b = TN2[find(c, TN2)];
			//b.print(); 
			A[a] = (b.US.find(a) != b.US.end());
			//print(TN2);
		}
	}
	//print(TN2);
	return A;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4


6 7 4
0 1
0 3
1 3
1 4
2 3
2 5
4 5
5 0 2 2
5 0 4 4
5 0 1 2
5 0 2 2
*/

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