oj.uz

Submission #421626

# Submission time Handle Problem Language Result Execution time Memory
421626 2021-06-09T10:12:38 Z amoo_safar Werewolf (IOI18_werewolf) C++17
100 / 100
 811 ms 87960 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;

int n, m, q;

vector<int> V[N], G[N];
int par[N];
int pos[N];

void Merge(int u, int v){
	u = par[u]; v = par[v];
	if(u == v) return ;
	if(V[u].size() > V[v].size()) swap(u, v);
	for(auto x : V[u]){
		pos[x] = V[v].size();
		par[x] = v;
		V[v].pb(x);
	}
	V[u].clear();
}

vector<pii> Q[2][N];
pii res[2][N];
vi arr[2];

void DSU(vi ord, int z){
	fill(pos, pos + n, 0);
	iota(par, par + n, 0);
	for(int i = 0; i < n; i++) V[i] = {i};

	vector<int> mk(n, 0);
	for(auto u : ord){
		mk[u] = 1;
		for(auto adj : G[u])
			if(mk[adj])
				Merge(adj, u);
		for(auto [id, v] : Q[z][u]){
			res[z][id] = {-pos[v], -pos[v] + ((int) V[par[v]].size())};
		}
	}
	for(auto u : ord)
		for(auto [id, v] : Q[z][u])
			res[z][id].F += pos[v], res[z][id].S += pos[v];
	arr[z] = V[par[0]];
}


typedef array<int, 3> que; // pos fac q_id
int sum[N];
vector<que> tsk[N];

int fen[N];
void AF(int idx, int x){
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += x;
}
int GF(int idx){
	int sm = 0;
	for(; idx; idx -= idx & (-idx))
		sm += fen[idx];
	return sm;
}

void Solve(){
	for(int i = 0; i < n; i++){
		// cerr << "! " << pos[arr[0][i]] << '\n';
		AF(pos[ arr[0][i] ] + 1, +1);
		for(auto [ps, fac, q_id] : tsk[i + 1]){
			sum[q_id] += fac * GF(ps);
		}
	}
}

vi check_validity(int _n, vi X, vi Y,
								vi S, vi E,
								vi L, vi R) {
	
	n = _n;
	m = X.size();
	q = S.size();
	
	for(int i = 0; i < q; i++){
		Q[0][R[i]].pb({i, E[i]});
		Q[1][L[i]].pb({i, S[i]});
	}

	for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);
	vector<int> ord(n, 0); iota(all(ord), 0);
	DSU(ord, 0);
	reverse(all(ord));
	DSU(ord, 1);

	// for(int i = 0; i < 2; i++){
	// 	cerr << "! ";
	// 	for(auto x : arr[i]) cerr << x << ' ';
	// 	cerr << '\n';
	// }

	for(int i = 0; i < q; i++){
		auto [l0, r0] = res[0][i];
		auto [l1, r1] = res[1][i];
		tsk[r0].pb({r1, +1, i});
		tsk[r0].pb({l1, -1, i});
		tsk[l0].pb({r1, -1, i});
		tsk[l0].pb({l1, +1, i});
		// cerr << "? [" << l0 << ", " << r0 << ") & [" << l1 << ' ' << r1 << ")\n";
		// break;
	}
	Solve();
	vector<int> ans;
	for(int i = 0; i < q; i++)
		ans.pb(sum[i] ? 1 : 0);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23792 KB Output is correct
2 Correct 17 ms 23792 KB Output is correct
3 Correct 16 ms 23884 KB Output is correct
4 Correct 17 ms 23864 KB Output is correct
5 Correct 17 ms 23824 KB Output is correct
6 Correct 19 ms 23784 KB Output is correct
7 Correct 18 ms 23868 KB Output is correct
8 Correct 17 ms 23884 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23792 KB Output is correct
2 Correct 17 ms 23792 KB Output is correct
3 Correct 16 ms 23884 KB Output is correct
4 Correct 17 ms 23864 KB Output is correct
5 Correct 17 ms 23824 KB Output is correct
6 Correct 19 ms 23784 KB Output is correct
7 Correct 18 ms 23868 KB Output is correct
8 Correct 17 ms 23884 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 23 ms 24764 KB Output is correct
11 Correct 22 ms 24744 KB Output is correct
12 Correct 23 ms 24864 KB Output is correct
13 Correct 23 ms 24788 KB Output is correct
14 Correct 25 ms 24808 KB Output is correct
15 Correct 24 ms 24788 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 87960 KB Output is correct
2 Correct 596 ms 77764 KB Output is correct
3 Correct 571 ms 80464 KB Output is correct
4 Correct 655 ms 82724 KB Output is correct
5 Correct 624 ms 82948 KB Output is correct
6 Correct 689 ms 84428 KB Output is correct
7 Correct 592 ms 85128 KB Output is correct
8 Correct 579 ms 77820 KB Output is correct
9 Correct 507 ms 79368 KB Output is correct
10 Correct 485 ms 82332 KB Output is correct
11 Correct 529 ms 84528 KB Output is correct
12 Correct 639 ms 85032 KB Output is correct
13 Correct 532 ms 77380 KB Output is correct
14 Correct 552 ms 77256 KB Output is correct
15 Correct 573 ms 77296 KB Output is correct
16 Correct 604 ms 77224 KB Output is correct
17 Correct 635 ms 84988 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23792 KB Output is correct
2 Correct 17 ms 23792 KB Output is correct
3 Correct 16 ms 23884 KB Output is correct
4 Correct 17 ms 23864 KB Output is correct
5 Correct 17 ms 23824 KB Output is correct
6 Correct 19 ms 23784 KB Output is correct
7 Correct 18 ms 23868 KB Output is correct
8 Correct 17 ms 23884 KB Output is correct
9 Correct 17 ms 23756 KB Output is correct
10 Correct 23 ms 24764 KB Output is correct
11 Correct 22 ms 24744 KB Output is correct
12 Correct 23 ms 24864 KB Output is correct
13 Correct 23 ms 24788 KB Output is correct
14 Correct 25 ms 24808 KB Output is correct
15 Correct 24 ms 24788 KB Output is correct
16 Correct 811 ms 87960 KB Output is correct
17 Correct 596 ms 77764 KB Output is correct
18 Correct 571 ms 80464 KB Output is correct
19 Correct 655 ms 82724 KB Output is correct
20 Correct 624 ms 82948 KB Output is correct
21 Correct 689 ms 84428 KB Output is correct
22 Correct 592 ms 85128 KB Output is correct
23 Correct 579 ms 77820 KB Output is correct
24 Correct 507 ms 79368 KB Output is correct
25 Correct 485 ms 82332 KB Output is correct
26 Correct 529 ms 84528 KB Output is correct
27 Correct 639 ms 85032 KB Output is correct
28 Correct 532 ms 77380 KB Output is correct
29 Correct 552 ms 77256 KB Output is correct
30 Correct 573 ms 77296 KB Output is correct
31 Correct 604 ms 77224 KB Output is correct
32 Correct 635 ms 84988 KB Output is correct
33 Correct 711 ms 81096 KB Output is correct
34 Correct 316 ms 64372 KB Output is correct
35 Correct 716 ms 78736 KB Output is correct
36 Correct 718 ms 81760 KB Output is correct
37 Correct 643 ms 79020 KB Output is correct
38 Correct 753 ms 80932 KB Output is correct
39 Correct 647 ms 78972 KB Output is correct
40 Correct 653 ms 79068 KB Output is correct
41 Correct 623 ms 78484 KB Output is correct
42 Correct 622 ms 80516 KB Output is correct
43 Correct 645 ms 79404 KB Output is correct
44 Correct 613 ms 79064 KB Output is correct
45 Correct 552 ms 77036 KB Output is correct
46 Correct 595 ms 78084 KB Output is correct
47 Correct 595 ms 77428 KB Output is correct
48 Correct 537 ms 77244 KB Output is correct
49 Correct 552 ms 77424 KB Output is correct
50 Correct 626 ms 77212 KB Output is correct
51 Correct 596 ms 78984 KB Output is correct
52 Correct 634 ms 79304 KB Output is correct