oj.uz

Submission #421580

# Submission time Handle Problem Language Result Execution time Memory
421580 2021-06-09T09:26:32 Z Keshi Werewolf (IOI18_werewolf) C++17
100 / 100
 3676 ms 357688 KB 
//In the name of God
#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

int n, m, q;
int dsu[maxn];
vector<int> g[maxn], vec[maxn], h[maxn];
vector<pll> com[maxn];
map<ll, ll> mp[maxn];

void init(bool f = 1){
	for(ll i = 0; i < n; i++){
		dsu[i] = i;
      	vec[i].clear();
		vec[i].reserve(10);
		vec[i].pb(i);
		if(f) mp[i][i] = n;
      	if(f) com[i].reserve(10);
		if(f) com[i].pb(Mp(i, n));
	}
}
bool Union(ll v, ll u, ll i){
	v = dsu[v];
	u = dsu[u];
	if(v == u) return 0;
	if(Sz(vec[v]) < Sz(vec[u])) swap(v, u);
	for(ll x : vec[u]){
		vec[v].pb(x);
		dsu[x] = v;
		mp[x][v] = i;
		com[x].pb(Mp(v, i));
	}
	return 1;
}
bool merge(ll v, ll u){
	v = dsu[v];
	u = dsu[u];
	if(v == u) return 0;
	if(Sz(vec[v]) < Sz(vec[u])) swap(v, u);
	for(ll x : vec[u]){
		vec[v].pb(x);
		dsu[x] = v;
	}
	for(pll x : mp[u]){
		mp[v][x.F] = max(mp[v][x.F], x.S);
	}
	return 1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	m = Sz(X);
	q = Sz(S);
	n = N;
	init();
	for(ll i = 0; i < m; i++){
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}
	for(ll i = 0; i < q; i++){
		h[R[i]].pb(i);
	}
	for(ll i = n; i--;){
		for(ll j : g[i]){
			if(j >= i) Union(i, j, i);
		}
	}
	init(0);
	vector<int> ans(q);
	for(ll i = 0; i < n; i++){
		for(ll j : g[i]){
			if(i >= j) merge(i, j);
		}
		for(ll j : h[i]){
			ll mx = 0;
			ll e = dsu[E[j]];
			for(pll x : com[S[j]]){
				mx = max(mx, min(x.S, mp[e][x.F]));
			}
			if(mx >= L[j]) ans[j] = 1;
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 17 ms 28492 KB Output is correct
3 Correct 16 ms 28392 KB Output is correct
4 Correct 16 ms 28500 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 15 ms 28520 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 17 ms 28492 KB Output is correct
3 Correct 16 ms 28392 KB Output is correct
4 Correct 16 ms 28500 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 15 ms 28520 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct
10 Correct 24 ms 29972 KB Output is correct
11 Correct 25 ms 30164 KB Output is correct
12 Correct 32 ms 31376 KB Output is correct
13 Correct 24 ms 29888 KB Output is correct
14 Correct 26 ms 30096 KB Output is correct
15 Correct 28 ms 30028 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3676 ms 357688 KB Output is correct
2 Correct 845 ms 123992 KB Output is correct
3 Correct 1035 ms 142524 KB Output is correct
4 Correct 1773 ms 176140 KB Output is correct
5 Correct 2108 ms 185916 KB Output is correct
6 Correct 2941 ms 235652 KB Output is correct
7 Correct 3047 ms 263748 KB Output is correct
8 Correct 683 ms 124012 KB Output is correct
9 Correct 758 ms 143076 KB Output is correct
10 Correct 1097 ms 166548 KB Output is correct
11 Correct 1676 ms 195000 KB Output is correct
12 Correct 1836 ms 186948 KB Output is correct
13 Correct 856 ms 118844 KB Output is correct
14 Correct 872 ms 118816 KB Output is correct
15 Correct 835 ms 118736 KB Output is correct
16 Correct 877 ms 118696 KB Output is correct
17 Correct 3020 ms 258672 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 17 ms 28492 KB Output is correct
3 Correct 16 ms 28392 KB Output is correct
4 Correct 16 ms 28500 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 17 ms 28492 KB Output is correct
8 Correct 15 ms 28520 KB Output is correct
9 Correct 16 ms 28492 KB Output is correct
10 Correct 24 ms 29972 KB Output is correct
11 Correct 25 ms 30164 KB Output is correct
12 Correct 32 ms 31376 KB Output is correct
13 Correct 24 ms 29888 KB Output is correct
14 Correct 26 ms 30096 KB Output is correct
15 Correct 28 ms 30028 KB Output is correct
16 Correct 3676 ms 357688 KB Output is correct
17 Correct 845 ms 123992 KB Output is correct
18 Correct 1035 ms 142524 KB Output is correct
19 Correct 1773 ms 176140 KB Output is correct
20 Correct 2108 ms 185916 KB Output is correct
21 Correct 2941 ms 235652 KB Output is correct
22 Correct 3047 ms 263748 KB Output is correct
23 Correct 683 ms 124012 KB Output is correct
24 Correct 758 ms 143076 KB Output is correct
25 Correct 1097 ms 166548 KB Output is correct
26 Correct 1676 ms 195000 KB Output is correct
27 Correct 1836 ms 186948 KB Output is correct
28 Correct 856 ms 118844 KB Output is correct
29 Correct 872 ms 118816 KB Output is correct
30 Correct 835 ms 118736 KB Output is correct
31 Correct 877 ms 118696 KB Output is correct
32 Correct 3020 ms 258672 KB Output is correct
33 Correct 2185 ms 175112 KB Output is correct
34 Correct 312 ms 49096 KB Output is correct
35 Correct 1345 ms 133340 KB Output is correct
36 Correct 1979 ms 196524 KB Output is correct
37 Correct 1414 ms 137884 KB Output is correct
38 Correct 1768 ms 175284 KB Output is correct
39 Correct 1615 ms 133008 KB Output is correct
40 Correct 1351 ms 136464 KB Output is correct
41 Correct 1039 ms 128728 KB Output is correct
42 Correct 1383 ms 150352 KB Output is correct
43 Correct 1012 ms 123608 KB Output is correct
44 Correct 1225 ms 135036 KB Output is correct
45 Correct 1075 ms 124928 KB Output is correct
46 Correct 1348 ms 135228 KB Output is correct
47 Correct 820 ms 118816 KB Output is correct
48 Correct 821 ms 119000 KB Output is correct
49 Correct 819 ms 118880 KB Output is correct
50 Correct 825 ms 118760 KB Output is correct
51 Correct 1368 ms 133492 KB Output is correct
52 Correct 1343 ms 133352 KB Output is correct