Submission #601883

#	Time	Username	Problem	Language	Result	Execution time	Memory
601883		idiot123	Werewolf (IOI18_werewolf)	C++14	100 / 100	963 ms	134512 KiB

werewolf

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

using namespace std;

int find(int a, vector<int>& rep){
	if(rep[a] != a)rep[a] = find(rep[a], rep);
	return rep[a];
}

void uni(int a, int b, vector<int>& rep, vector<set<int>>& pos){
	a = find(a, rep); b = find(b, rep);
	if(a != b){
		if(pos[a].size() < pos[b].size())swap(a, b);
		rep[b] = a;
		pos[a].insert(pos[b].begin(), pos[b].end());
		pos[b].clear();
	}
}

void computeRange(int v, vector<pair<int, int>>& children, vector<pair<int, int>>& range, int& cnt){
	if(children[v] == make_pair(-1, -1)){
		range[v] = {cnt, cnt}; cnt++;
	}else{
		computeRange(children[v].first, children, range, cnt);
		computeRange(children[v].second, children, range, cnt);
		range[v] = {range[children[v].first].first, range[children[v].second].second};
	}
}

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();
	int Q = S.size();
	vector<vector<int>> smaller(N);
	vector<vector<int>> bigger(N);
	for(int j = 0; j < M; j++){
		int x, y; x = X[j]; y = Y[j];
		if(x > y)swap(x, y);
		bigger[x].push_back(y);
		smaller[y].push_back(x);
	}
	vector<array<int, 20>> jump(N);
	vector<array<int, 20>> jumpR(N);
	vector<pair<int, int>> children(N, {-1, -1});
	vector<int> repR(N); for(int i = 0; i < N; i++)repR[i] = i;
	int id = N;
	//cout<<"WOW\n";
	for(int r = 1; r < N; r++){
		for(auto l : smaller[r]){
			int x = find(l, repR); int y = find(r, repR);
			if(x != y){
				repR.push_back(id);
				jump.push_back(array<int, 20>());
				jumpR.push_back(array<int, 20>()); 
				jump[x][0] = id; jump[y][0] = id; 
				repR[x] = id; repR[y] = id;
				jumpR[x][0] = r; jumpR[y][0] = r;
				jump[id][0] = id;
				jumpR[id][0] = r;
				id++;
				children.push_back({x, y});
			}
		}
	}
	//cout<<"XD\n";
	vector<pair<int, int>> range(id);
	int cnt = 0;
	computeRange(id-1, children, range, cnt);
	/*for(int i = 0; i < id; i++){
		cout<<children[i].first<<" "<<children[i].second<<"     "<<jump[i][0]<<" "<<jumpR[i][0]<<"      "<<range[i].first<<" "<<range[i].second<<"\n";
	}*/
	vector<int> A(Q);
	for(int k=  1; k < 20; k++){
		for(int i = 0; i < id; i++){
			jump[i][k] = jump[jump[i][k-1]][k-1];
			jumpR[i][k] = jumpR[jump[i][k-1]][k-1];
		}
	}
	vector<array<int, 3>> queries;
	vector<int> rep(N);
	for(int i=  0; i < N; i++)rep[i] = i;
	vector<set<int>> pos(N);
	for(int i = 0; i < N; i++)pos[i].insert(range[i].first);
	for(int i =0; i < Q; i++){
		queries.push_back({L[i], R[i], i});
	}
	sort(queries.begin(), queries.end(), greater<array<int, 3>>());
	int currentL = N-1;
	for(auto query : queries){
		int L = query[0]; int R = query[1]; int ansId = query[2];
		while(L < currentL){
			currentL--;
			for(auto x : bigger[currentL]){
				uni(x, currentL, rep, pos);
			}
		}
		int v = E[ansId];
		for(int k = 19; k >= 0; k--){
			if(jumpR[v][k] <= R){
				v = jump[v][k];
			}
		}
		int x = S[ansId];
		x = find(x, rep);
		auto it = pos[x].lower_bound(range[v].first);
		if(it != pos[x].end() && (*it) <= range[v].second){
			A[ansId] = 1;
		}else{
			A[ansId] = 0;
		}
	}
	return A;
}

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