oj.uz

Submission #294029

# Submission time Handle Problem Language Result Execution time Memory
294029 2020-09-08T14:32:00 Z Saboon Werewolf (IOI18_werewolf) C++17
100 / 100
 3119 ms 148332 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4e5 + 10;
const int N = 2e5 + 10;
vector<int> fex[N], fen[N];

void addinit(int x, int y){ // 0-index
	x ++, y ++;
	for (; x < N; x += x & -x)
		fex[x].push_back(y);
}

void add(int x, int y){
    x ++, y ++;
	for (; x < N; x += x & -x){
		int idy = lower_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin()+1;
		for (; idy < fen[x].size(); idy += idy & -idy)
			fen[x][idy] ++;
	}
}

int get(int x, int y){
    x ++, y ++;
	int ret = 0;
	for (; x; x -= x & -x){
		int idy = upper_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin();
		for (; idy; idy -= idy & -idy)
			ret += fen[x][idy];
	}
	return ret;
}

int get(int l1, int l2, int r1, int r2){
	return get(l2, r2) - get(l2,r1-1) - get(l1-1,r2) + get(l1-1,r1-1); 
}

struct DSU{
	int n;
	int p[maxn], w[maxn], lo[maxn], hi[maxn], lc[maxn], rc[maxn];
	int par[maxn][18];
	int newint, Time;
	DSU(int n_ = 0){
		n = n_, newint = n, Time = 0;
		memset(p, -1, sizeof p);
		memset(par, -1, sizeof par);
	}
	int get_par(int v){
		return p[v] < 0 ? v : p[v] = get_par(p[v]);
	}
	void merge(int v, int u, int weight){
		int Tv = v, Tu = u;
		if ((v = get_par(v)) == (u = get_par(u)))
			return;
		int me = newint ++;
		p[v] = p[u] = me;
		par[v][0] = par[u][0] = me;
		w[me] = weight;
		lc[me] = v, rc[me] = u;
	}
	void dfs(int v){
		if (v < n){
			lo[v] = Time, hi[v] = Time;
			Time ++;
			return;
		}
		lo[v] = Time;
		dfs(lc[v]);
		dfs(rc[v]);
		hi[v] = Time-1;
	}
	void init(){
		for (int v = newint-1; v >= 0; v--)
			for (int i = 1; i < 18 and par[v][i-1] != -1; i++)
				par[v][i] = par[par[v][i-1]][i-1];
		dfs(newint-1);
	}
	int getRoot(int v, int weight){
		for (int i = 17; i >= 0; i--)
			if (par[v][i] != -1 and w[par[v][i]] <= weight)
				v = par[v][i];
		return v;
	}
};

vector<int> g[maxn];

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(), Q = S.size();
	for (int i = 0; i < m; i++){
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
		
	}
	DSU T1 = DSU(n), T2 = DSU(n);
	for (int v = 0; v < n; v++)
		for (auto u : g[v])
			if (u < v)
				T1.merge(v,u,v);
	for (int v = n-1; v >= 0; v--)
		for (auto u : g[v])
			if (u > v)
				T2.merge(v,u,-v);
	T1.init();
	T2.init();
	for (int v = 0; v < n; v++)
		addinit(T1.lo[v], T2.lo[v]);
	for (int i = 0; i < N; i++){
		sort(fex[i].begin(), fex[i].end());
		fex[i].resize(unique(fex[i].begin(),fex[i].end())-fex[i].begin());
		fen[i].resize(fex[i].size()+2);
	}
	for (int v = 0; v < n; v++)
		add(T1.lo[v], T2.lo[v]);
	vector<int> A(Q);
	for (int i = 0; i < Q; ++i){
		int v = T1.getRoot(E[i],R[i]);
		int u = T2.getRoot(S[i],-L[i]);
		int sum = get(T1.lo[v], T1.hi[v], T2.lo[u], T2.hi[u]);
		A[i] = (sum > 0);
	}
	return A;
}

Compilation message

werewolf.cpp: In function 'void add(int, int)':
werewolf.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (; idy < fen[x].size(); idy += idy & -idy)
      |          ~~~~^~~~~~~~~~~~~~~
werewolf.cpp: In member function 'void DSU::merge(int, int, int)':
werewolf.cpp:53:7: warning: unused variable 'Tv' [-Wunused-variable]
   53 |   int Tv = v, Tu = u;
      |       ^~
werewolf.cpp:53:15: warning: unused variable 'Tu' [-Wunused-variable]
   53 |   int Tv = v, Tu = u;
      |               ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 84984 KB Output is correct
2 Correct 60 ms 84988 KB Output is correct
3 Correct 57 ms 84984 KB Output is correct
4 Correct 57 ms 84960 KB Output is correct
5 Correct 60 ms 84984 KB Output is correct
6 Correct 58 ms 84984 KB Output is correct
7 Correct 65 ms 84976 KB Output is correct
8 Correct 62 ms 84984 KB Output is correct
9 Correct 62 ms 84972 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 84984 KB Output is correct
2 Correct 60 ms 84988 KB Output is correct
3 Correct 57 ms 84984 KB Output is correct
4 Correct 57 ms 84960 KB Output is correct
5 Correct 60 ms 84984 KB Output is correct
6 Correct 58 ms 84984 KB Output is correct
7 Correct 65 ms 84976 KB Output is correct
8 Correct 62 ms 84984 KB Output is correct
9 Correct 62 ms 84972 KB Output is correct
10 Correct 77 ms 85912 KB Output is correct
11 Correct 85 ms 85880 KB Output is correct
12 Correct 75 ms 85828 KB Output is correct
13 Correct 90 ms 85952 KB Output is correct
14 Correct 77 ms 85924 KB Output is correct
15 Correct 83 ms 85884 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2237 ms 130408 KB Output is correct
2 Correct 2059 ms 133320 KB Output is correct
3 Correct 1961 ms 139616 KB Output is correct
4 Correct 1688 ms 138864 KB Output is correct
5 Correct 1669 ms 138800 KB Output is correct
6 Correct 1862 ms 138536 KB Output is correct
7 Correct 1621 ms 138556 KB Output is correct
8 Correct 2039 ms 141676 KB Output is correct
9 Correct 1585 ms 139724 KB Output is correct
10 Correct 1027 ms 138792 KB Output is correct
11 Correct 1189 ms 138668 KB Output is correct
12 Correct 1551 ms 138736 KB Output is correct
13 Correct 1751 ms 141804 KB Output is correct
14 Correct 1741 ms 141676 KB Output is correct
15 Correct 1778 ms 141676 KB Output is correct
16 Correct 1711 ms 141932 KB Output is correct
17 Correct 1639 ms 138664 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 84984 KB Output is correct
2 Correct 60 ms 84988 KB Output is correct
3 Correct 57 ms 84984 KB Output is correct
4 Correct 57 ms 84960 KB Output is correct
5 Correct 60 ms 84984 KB Output is correct
6 Correct 58 ms 84984 KB Output is correct
7 Correct 65 ms 84976 KB Output is correct
8 Correct 62 ms 84984 KB Output is correct
9 Correct 62 ms 84972 KB Output is correct
10 Correct 77 ms 85912 KB Output is correct
11 Correct 85 ms 85880 KB Output is correct
12 Correct 75 ms 85828 KB Output is correct
13 Correct 90 ms 85952 KB Output is correct
14 Correct 77 ms 85924 KB Output is correct
15 Correct 83 ms 85884 KB Output is correct
16 Correct 2237 ms 130408 KB Output is correct
17 Correct 2059 ms 133320 KB Output is correct
18 Correct 1961 ms 139616 KB Output is correct
19 Correct 1688 ms 138864 KB Output is correct
20 Correct 1669 ms 138800 KB Output is correct
21 Correct 1862 ms 138536 KB Output is correct
22 Correct 1621 ms 138556 KB Output is correct
23 Correct 2039 ms 141676 KB Output is correct
24 Correct 1585 ms 139724 KB Output is correct
25 Correct 1027 ms 138792 KB Output is correct
26 Correct 1189 ms 138668 KB Output is correct
27 Correct 1551 ms 138736 KB Output is correct
28 Correct 1751 ms 141804 KB Output is correct
29 Correct 1741 ms 141676 KB Output is correct
30 Correct 1778 ms 141676 KB Output is correct
31 Correct 1711 ms 141932 KB Output is correct
32 Correct 1639 ms 138664 KB Output is correct
33 Correct 2675 ms 139628 KB Output is correct
34 Correct 547 ms 115832 KB Output is correct
35 Correct 2961 ms 142048 KB Output is correct
36 Correct 2615 ms 139092 KB Output is correct
37 Correct 3119 ms 141364 KB Output is correct
38 Correct 2787 ms 139724 KB Output is correct
39 Correct 2136 ms 145196 KB Output is correct
40 Correct 1953 ms 147688 KB Output is correct
41 Correct 2450 ms 140860 KB Output is correct
42 Correct 1681 ms 139468 KB Output is correct
43 Correct 2949 ms 145392 KB Output is correct
44 Correct 2793 ms 141420 KB Output is correct
45 Correct 1793 ms 145396 KB Output is correct
46 Correct 2009 ms 145140 KB Output is correct
47 Correct 1761 ms 141768 KB Output is correct
48 Correct 1743 ms 141608 KB Output is correct
49 Correct 1737 ms 141804 KB Output is correct
50 Correct 1723 ms 141824 KB Output is correct
51 Correct 1791 ms 148132 KB Output is correct
52 Correct 1784 ms 148332 KB Output is correct