oj.uz

Submission #119366

# Submission time Handle Problem Language Result Execution time Memory
119366 2019-06-21T05:50:41 Z 김세빈(#2918) Werewolf (IOI18_werewolf) C++14
100 / 100
 2025 ms 149764 KB 
#include <bits/stdc++.h>

#include "werewolf.h"

using namespace std;

typedef pair <int, int> pii;

struct edge{
	int u, v, c;
	edge() {}
	edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

struct tree{
	vector <edge> E;
	vector <int> T[505050];
	int P[18][505050];
	int U[505050], C[505050];
	int L[505050], R[505050];
	int n, k, t;
	
	int find(int p) { return p == U[p]? p : U[p] = find(U[p]); }
	
	void init(int _N)
	{
		int i;
		
		n = _N;
		
		for(i=0; i<n+n; i++){
			U[i] = i;
		}
		
		k = n - 1;
	}
	
	void add_edge(int u, int v, int c) { E.emplace_back(u, v, c); }
	
	void dfs(int p, int r)
	{
		P[0][p] = r; L[p] = t;
		if(p < n) t ++;
		
		for(int &t: T[p]){
			dfs(t, p);
		}
		
		R[p] = t - 1;
	}
	
	void make()
	{
		int i, j;
		
		sort(E.begin(), E.end(), [&](edge &ea, edge &eb){
			return ea.c < eb.c;
		});
		
		for(edge &e: E){
			if(find(e.u) != find(e.v)){
				k ++; C[k] = e.c;
				T[k].push_back(find(e.u));
				T[k].push_back(find(e.v));
				U[find(e.u)] = k;
				U[find(e.v)] = k;
			}
		}
		
		t = 0; dfs(k, k);
		
		for(i=1; i<=18; i++){
			for(j=0; j<=k; j++){
				P[i][j] = P[i - 1][P[i - 1][j]];
			}
		}
	}
	
	pii find_intv(int p, int c)
	{
		int i;
		
		for(i=18; i>=0; i--){
			if(C[P[i][p]] <= c) p = P[i][p];
		}
		
		return pii(L[p], R[p]);
	}
	
	int get_id(int p) { return L[p]; }
};

int T[606060], P[202020];
vector <pii> Q[202020];
tree T1, T2;
int n, sz;

void update(int p, int v)
{
	p += sz; T[p] = v;
	for(p>>=1; p; p>>=1){
		T[p] = max(T[p << 1], T[p << 1 | 1]);
	}
}

int get_max(int l, int r)
{
	int ret = 0;
	
	l += sz; r += sz;
	
	for(; l<r; ){
		if(l & 1) ret = max(ret, T[l]);
		if(~r & 1) ret = max(ret, T[r]);
		l = l + 1 >> 1;
		r = r - 1 >> 1;
	}
	
	if(l == r){
		ret = max(ret, T[l]);
	}
	
	return ret;
}

vector <int> check_validity(int _N, vector <int> X, vector <int> Y, 
	vector <int> S, vector <int> E, vector <int> L, vector <int> R)
{
	vector <int> A(S.size());
	int i, j, l, r;
	
	n = _N;
	
	T1.init(n); T2.init(n);
	
	for(i=0; i<X.size(); i++){
		T1.add_edge(X[i], Y[i], n - 1 - min(X[i], Y[i]));
		T2.add_edge(X[i], Y[i], max(X[i], Y[i]));
	}
	
	T1.make(); T2.make();
	
	for(sz=1; sz<n; sz<<=1);
	
	for(i=0; i<n; i++){
		P[T1.get_id(i)] = T2.get_id(i);
	}
	
	for(i=0; i<S.size(); i++){
		tie(l, r) = T1.find_intv(S[i], n - 1 - L[i]);
		Q[r].emplace_back(l, i);
	}
	
	for(i=0; i<n; i++){
		update(P[i], i + 1);
		for(pii t: Q[i]){
			tie(l, r) = T2.find_intv(E[t.second], R[t.second]);
			A[t.second] = (get_max(l, r) > t.first);
		}
	}
	
	return A;
}

Compilation message

werewolf.cpp: In function 'int get_max(int, int)':
werewolf.cpp:115:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l + 1 >> 1;
       ~~^~~
werewolf.cpp:116:9: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r - 1 >> 1;
       ~~^~~
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:136:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<X.size(); i++){
           ~^~~~~~~~~
werewolf.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<S.size(); i++){
           ~^~~~~~~~~
werewolf.cpp:130:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, l, r;
         ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29184 KB Output is correct
2 Correct 28 ms 29184 KB Output is correct
3 Correct 27 ms 29176 KB Output is correct
4 Correct 27 ms 29184 KB Output is correct
5 Correct 27 ms 29176 KB Output is correct
6 Correct 26 ms 29184 KB Output is correct
7 Correct 27 ms 29304 KB Output is correct
8 Correct 26 ms 29176 KB Output is correct
9 Correct 30 ms 29156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29184 KB Output is correct
2 Correct 28 ms 29184 KB Output is correct
3 Correct 27 ms 29176 KB Output is correct
4 Correct 27 ms 29184 KB Output is correct
5 Correct 27 ms 29176 KB Output is correct
6 Correct 26 ms 29184 KB Output is correct
7 Correct 27 ms 29304 KB Output is correct
8 Correct 26 ms 29176 KB Output is correct
9 Correct 30 ms 29156 KB Output is correct
10 Correct 38 ms 30840 KB Output is correct
11 Correct 36 ms 30840 KB Output is correct
12 Correct 38 ms 30852 KB Output is correct
13 Correct 36 ms 30840 KB Output is correct
14 Correct 37 ms 30848 KB Output is correct
15 Correct 36 ms 30972 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1851 ms 129880 KB Output is correct
2 Correct 1725 ms 140288 KB Output is correct
3 Correct 1590 ms 138036 KB Output is correct
4 Correct 1485 ms 137196 KB Output is correct
5 Correct 1494 ms 137240 KB Output is correct
6 Correct 1685 ms 137628 KB Output is correct
7 Correct 1518 ms 137112 KB Output is correct
8 Correct 1245 ms 140312 KB Output is correct
9 Correct 707 ms 138040 KB Output is correct
10 Correct 485 ms 136988 KB Output is correct
11 Correct 587 ms 136984 KB Output is correct
12 Correct 593 ms 136856 KB Output is correct
13 Correct 1734 ms 140836 KB Output is correct
14 Correct 1864 ms 140824 KB Output is correct
15 Correct 1718 ms 140864 KB Output is correct
16 Correct 1703 ms 140780 KB Output is correct
17 Correct 1503 ms 137348 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29184 KB Output is correct
2 Correct 28 ms 29184 KB Output is correct
3 Correct 27 ms 29176 KB Output is correct
4 Correct 27 ms 29184 KB Output is correct
5 Correct 27 ms 29176 KB Output is correct
6 Correct 26 ms 29184 KB Output is correct
7 Correct 27 ms 29304 KB Output is correct
8 Correct 26 ms 29176 KB Output is correct
9 Correct 30 ms 29156 KB Output is correct
10 Correct 38 ms 30840 KB Output is correct
11 Correct 36 ms 30840 KB Output is correct
12 Correct 38 ms 30852 KB Output is correct
13 Correct 36 ms 30840 KB Output is correct
14 Correct 37 ms 30848 KB Output is correct
15 Correct 36 ms 30972 KB Output is correct
16 Correct 1851 ms 129880 KB Output is correct
17 Correct 1725 ms 140288 KB Output is correct
18 Correct 1590 ms 138036 KB Output is correct
19 Correct 1485 ms 137196 KB Output is correct
20 Correct 1494 ms 137240 KB Output is correct
21 Correct 1685 ms 137628 KB Output is correct
22 Correct 1518 ms 137112 KB Output is correct
23 Correct 1245 ms 140312 KB Output is correct
24 Correct 707 ms 138040 KB Output is correct
25 Correct 485 ms 136988 KB Output is correct
26 Correct 587 ms 136984 KB Output is correct
27 Correct 593 ms 136856 KB Output is correct
28 Correct 1734 ms 140836 KB Output is correct
29 Correct 1864 ms 140824 KB Output is correct
30 Correct 1718 ms 140864 KB Output is correct
31 Correct 1703 ms 140780 KB Output is correct
32 Correct 1503 ms 137348 KB Output is correct
33 Correct 2000 ms 138652 KB Output is correct
34 Correct 395 ms 66440 KB Output is correct
35 Correct 1863 ms 141468 KB Output is correct
36 Correct 1883 ms 138496 KB Output is correct
37 Correct 2025 ms 140568 KB Output is correct
38 Correct 1973 ms 139096 KB Output is correct
39 Correct 1868 ms 144280 KB Output is correct
40 Correct 1295 ms 149764 KB Output is correct
41 Correct 901 ms 139288 KB Output is correct
42 Correct 660 ms 137628 KB Output is correct
43 Correct 1431 ms 146248 KB Output is correct
44 Correct 1393 ms 140104 KB Output is correct
45 Correct 908 ms 143768 KB Output is correct
46 Correct 945 ms 143256 KB Output is correct
47 Correct 1778 ms 141080 KB Output is correct
48 Correct 1725 ms 140716 KB Output is correct
49 Correct 1691 ms 141200 KB Output is correct
50 Correct 1772 ms 140764 KB Output is correct
51 Correct 984 ms 149444 KB Output is correct
52 Correct 1004 ms 149412 KB Output is correct