oj.uz

Submission #75230

# Submission time Handle Problem Language Result Execution time Memory
75230 2018-09-08T17:29:02 Z tincamatei Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 327972 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20728 KB Output is correct
2 Correct 23 ms 20852 KB Output is correct
3 Correct 21 ms 20852 KB Output is correct
4 Correct 21 ms 20852 KB Output is correct
5 Correct 27 ms 20864 KB Output is correct
6 Correct 21 ms 20880 KB Output is correct
7 Correct 21 ms 20884 KB Output is correct
8 Correct 20 ms 20944 KB Output is correct
9 Correct 23 ms 20996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20728 KB Output is correct
2 Correct 23 ms 20852 KB Output is correct
3 Correct 21 ms 20852 KB Output is correct
4 Correct 21 ms 20852 KB Output is correct
5 Correct 27 ms 20864 KB Output is correct
6 Correct 21 ms 20880 KB Output is correct
7 Correct 21 ms 20884 KB Output is correct
8 Correct 20 ms 20944 KB Output is correct
9 Correct 23 ms 20996 KB Output is correct
10 Correct 30 ms 22472 KB Output is correct
11 Correct 44 ms 22532 KB Output is correct
12 Correct 42 ms 24048 KB Output is correct
13 Correct 30 ms 24048 KB Output is correct
14 Correct 32 ms 24048 KB Output is correct
15 Correct 36 ms 24048 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4034 ms 327972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20728 KB Output is correct
2 Correct 23 ms 20852 KB Output is correct
3 Correct 21 ms 20852 KB Output is correct
4 Correct 21 ms 20852 KB Output is correct
5 Correct 27 ms 20864 KB Output is correct
6 Correct 21 ms 20880 KB Output is correct
7 Correct 21 ms 20884 KB Output is correct
8 Correct 20 ms 20944 KB Output is correct
9 Correct 23 ms 20996 KB Output is correct
10 Correct 30 ms 22472 KB Output is correct
11 Correct 44 ms 22532 KB Output is correct
12 Correct 42 ms 24048 KB Output is correct
13 Correct 30 ms 24048 KB Output is correct
14 Correct 32 ms 24048 KB Output is correct
15 Correct 36 ms 24048 KB Output is correct
16 Execution timed out 4034 ms 327972 KB Time limit exceeded
17 Halted 0 ms 0 KB -