Submission #75230

#	Time	Username	Problem	Language	Result	Execution time	Memory
75230		tincamatei	Werewolf (IOI18_werewolf)	C++14	15 / 100	4034 ms	327972 KiB

werewolf

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

using namespace std;

const int MAX_N = 200000;

vector<int> graph[MAX_N];
vector<pair<int, int> > components[MAX_N];

struct CompEdge {
	int a, b, timestamp1, timestamp2;
};

vector<CompEdge> edges;

int currComp[MAX_N];
int sizeComp[MAX_N];
int poz[MAX_N];

void dfs(int nod, int oldComp, int newComp, int timestamp) {
	sizeComp[oldComp]--;
	sizeComp[newComp]++;
	currComp[nod] = newComp;
	components[nod].push_back(make_pair(newComp, timestamp));
	for(auto it: graph[nod])
		if(currComp[it] == oldComp)
			dfs(it, oldComp, newComp, timestamp);
}

void mergeComps(int a, int b, int timestamp) {
	if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
		swap(a, b);
	dfs(b, currComp[b], currComp[a], timestamp);
}

void dfs2(int nod, int oldComp, int newComp, int timestamp) {
	for(auto it: components[nod])
		edges.push_back({it.first, newComp, it.second, timestamp});
	sizeComp[oldComp]--;
	sizeComp[newComp]++;
	currComp[nod] = newComp;
	for(auto it: graph[nod])
		if(currComp[it] == oldComp)
			dfs2(it, oldComp, newComp, timestamp);
}

void mergeComps2(int a, int b, int timestamp) {
	if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
		swap(a, b);
	dfs2(b, currComp[b], currComp[a], timestamp);
}

void dfs3(int nod, int oldComp, int newComp) {
	sizeComp[oldComp]--;
	sizeComp[newComp]++;
	currComp[nod] = newComp;
	for(auto it: graph[nod])
		if(currComp[it] == oldComp)
			dfs3(it, oldComp, newComp);
}

void mergeComps3(int a, int b) {
	if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
		swap(a, b);
	dfs3(b, currComp[b], currComp[a]);
}


int pozQ[MAX_N];

std::vector<int> LQ;

bool cmp(int a, int b) {
	return LQ[a] > LQ[b];
}

unordered_map<int, int> firstTime[MAX_N];

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int Q = S.size();
	LQ = L;
	
	std::vector<int> rez(Q);

	for(int i = 0; i < Q; ++i)
		pozQ[i] = i;

	std::sort(pozQ, pozQ + Q, cmp);

	for(int i = 0; i < X.size(); ++i) {
		graph[X[i]].push_back(Y[i]);
		graph[Y[i]].push_back(X[i]);
	}

	for(int i = 0; i < N; ++i) {
		currComp[i] = i;
		sizeComp[i] = 1;
	}

	for(int i = 0; i < N; ++i) {
		components[i].push_back(make_pair(i, 0));
		for(auto it: graph[i])
			if(it < i && currComp[i] != currComp[it])
				mergeComps(it, i, i);
	}

	for(int i = 0; i < N; ++i) {
		currComp[i] = i;
		sizeComp[i] = 1;
	}
	for(int i = N - 1; i >= 0; --i) {
		for(auto it: components[i])
			edges.push_back({it.first, i, it.second, i});
		for(auto it: graph[i])
			if(it > i && currComp[it] != currComp[i]) {
				mergeComps2(it, i, i);
			}
	}
	
	for(int i = 0; i < N; ++i) {
		currComp[i] = i;
		sizeComp[i] = 1;
	}

	int lastup = N - 1;
	int lastE = 0;

	for(int i = 0; i < Q; ++i) {
		int l, r, s, e;
		l = L[pozQ[i]];
		r = R[pozQ[i]];
		s = S[pozQ[i]];
		e = E[pozQ[i]];
		
		while(lastup >= l) {
			for(auto it: graph[lastup])
				if(lastup < it && currComp[lastup] != currComp[it])
					mergeComps3(it, lastup);
			--lastup;
		}
		
		while(lastE < edges.size() && edges[lastE].timestamp2 >= l) {
			if(edges[lastE].timestamp2 <= edges[lastE].timestamp2) {
				int a = edges[lastE].a, b = edges[lastE].b, ts = edges[lastE].timestamp1;
				firstTime[a][b] = min(firstTime[a][b], ts - MAX_N);
			}
			++lastE;
		}

		int compS, compE = currComp[s];
		int stB = 0, drB = components[e].size();

		while(drB - stB > 1) {
			int mid = (stB + drB) / 2;
			if(components[e][mid].second <= r)
				stB = mid;
			else
				drB = mid;
		}
		compS = components[e][stB].first;
		
		if(firstTime[compS][compE] + MAX_N <= r)
			rez[pozQ[i]] = true;
		else
			rez[pozQ[i]] = false;
	}

	return rez;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); ++i) {
                 ~~^~~~~~~~~~
werewolf.cpp:145:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(lastE < edges.size() && edges[lastE].timestamp2 >= l) {
         ~~~~~~^~~~~~~~~~~~~~

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