oj.uz

Submission #769218

# Submission time Handle Problem Language Result Execution time Memory
769218 2023-06-29T10:03:33 Z khshg Werewolf (IOI18_werewolf) C++14
34 / 100
 245 ms 37708 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> adj;
vector<int> D;
vector<pair<int, int>> range;

void init(int N) {
	D = vector<int>(N, -1);
	range.resize(N);
	for(int i = 0; i < N; ++i) {
		range[i] = {i, i};
	}
}

int parent(int x) {
	return (D[x] < 0 ? x : D[x] = parent(D[x]));
}

pair<int, int> range_of_ind(int i) {
	return range[parent(i)];
}

void unite(int x, int y) {
	x = parent(x); y = parent(y);
	if(x == y) return;
	if(D[x] > D[y]) swap(x, y);
	range[x].first = min(range[x].first, range[y].first);
	range[x].second = max(range[x].second, range[y].second);
	D[x] += D[y];
	D[y] = x;
}
 
vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = _N;
	adj.resize(N);
	int M = (int)X.size();
	for(int i = 0; i < M; ++i) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	vector<int> flat(N), pos(N);
	{
		int root;
		for(int i = 0; i < N; ++i) if((int)adj[i].size() == 1) { root = i; break; }
		int cur = root, prev = -1;
		for(int i = 0; i < N; ++i) {
			flat[i] = cur;
			pos[cur] = i;
			if(i == N - 1) continue;
			bool f = (adj[cur][0] == prev);
			prev = cur;
			cur = adj[cur][f];
		}
	}
	int Q = (int)L.size();
	vector<int> sind(Q);
	iota(begin(sind), end(sind), 0);
	sort(begin(sind), end(sind), [&](const int i, const int j) { return L[i] < L[j]; });
	int do_now = N - 1;
	init(N);
	vector<int> SL(Q), SR(Q), EL(Q), ER(Q);
	for(int i = Q - 1; i >= 0; --i) {
		int ind = sind[i];
		while(do_now >= L[ind]) {
			for(auto& u : adj[do_now]) {
				if(u >= do_now) unite(pos[u], pos[do_now]);
			}
			--do_now;
		}
		tie(SL[ind], SR[ind]) = range_of_ind(pos[S[ind]]);
	}
	init(N);
	sort(begin(sind), end(sind), [&](const int i, const int j) { return R[i] < R[j]; });
	do_now = 0;
	for(int i = 0; i < Q; ++i) {
		int ind = sind[i];
		while(do_now <= R[ind]) {
			for(auto& u : adj[do_now]) {
				if(u <= do_now) unite(pos[u], pos[do_now]);
			}
			++do_now;
		}
		tie(EL[ind], ER[ind]) = range_of_ind(pos[E[ind]]);
	}
	vector<int> ans(Q);
	for(int i = 0; i < Q; ++i) {
		ans[i] = !((EL[i] > SR[i]) || (SL[i] > ER[i]));
	}
	return ans;
}

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:51:11: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |    pos[cur] = i;
      |           ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 29304 KB Output is correct
2 Correct 221 ms 37708 KB Output is correct
3 Correct 218 ms 37696 KB Output is correct
4 Correct 233 ms 37640 KB Output is correct
5 Correct 225 ms 37708 KB Output is correct
6 Correct 245 ms 37692 KB Output is correct
7 Correct 239 ms 37636 KB Output is correct
8 Correct 213 ms 37640 KB Output is correct
9 Correct 187 ms 37640 KB Output is correct
10 Correct 219 ms 37624 KB Output is correct
11 Correct 220 ms 37620 KB Output is correct
12 Correct 223 ms 37620 KB Output is correct
13 Correct 226 ms 37620 KB Output is correct
14 Correct 216 ms 37624 KB Output is correct
15 Correct 234 ms 37636 KB Output is correct
16 Correct 224 ms 37624 KB Output is correct
17 Correct 242 ms 37620 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -