oj.uz

Submission #421565

# Submission time Handle Problem Language Result Execution time Memory
421565 2021-06-09T09:12:29 Z alishahali1382 Werewolf (IOI18_werewolf) C++14
100 / 100
 1959 ms 146032 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=300010, LOG=18;

int n, m, k, x, y, u, v, timer, ans;
int par1[LOG][MAXN];
int par2[LOG][MAXN];
int dsu[MAXN];
int stt1[MAXN], fnt1[MAXN];
int stt2[MAXN], fnt2[MAXN];
vector<int> G[MAXN];
vector<int> seg[MAXN<<2];

int getpar(int x){ return (dsu[x]==x?x:dsu[x]=getpar(dsu[x]));}
void dfs1(int node, int stt[], int fnt[]){
	stt[node]=timer++;
	for (int v:G[node]) dfs1(v, stt, fnt);
	fnt[node]=timer;
}
void Add(int id, int tl, int tr, int pos, int val){
	if (pos<tl || tr<=pos) return ;
	seg[id].pb(val);
	if (tr-tl==1) return ;
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, pos, val);
	Add(id<<1 | 1, mid, tr, pos, val);
}
int Get(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return inf;
	if (l<=tl && tr<=r) return *lower_bound(all(seg[id]), val);
	int mid=(tl+tr)>>1;
	return min(Get(id<<1, tl, mid, l, r, val), Get(id<<1 | 1, mid, tr, l, r, val));
}
bool Solve(int y, int x, int l, int r){ // go from y to x
	for (int i=LOG-1; ~i; i--) if (par1[i][x] && par1[i][x]<=r) x=par1[i][x];
	for (int i=LOG-1; ~i; i--) if (par2[i][y] && par2[i][y]>=l) y=par2[i][y];
	return Get(1, 1, n+1, stt1[x], fnt1[x], stt2[y])<fnt2[y];
}

vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R){
	n=_n;
	m=SZ(X);
	while (m--){
		int u=X[m], v=Y[m];
		u++;
		v++;
		G[u].pb(v);
		G[v].pb(u);
	}
	iota(dsu+1, dsu+n+1, 1);
	for (int i=1; i<=n; i++){
		for (int j:G[i]) if (j<i){
			int x=getpar(j);
			if (x==i) continue ;
			par1[0][x]=i;
			dsu[x]=i;
		}
	}
	iota(dsu+1, dsu+n+1, 1);
	for (int i=n; i; i--){
		for (int j:G[i]) if (j>i){
			int x=getpar(j);
			if (x==i) continue ;
			// debug2(x, i)
			par2[0][x]=i;
			dsu[x]=i;
		}
	}
	for (int i=1; i<=n; i++) G[i].clear();
	for (int i=1; i<n; i++) G[par1[0][i]].pb(i);
	timer=1;
	dfs1(n, stt1, fnt1);
	
	for (int i=1; i<=n; i++) G[i].clear();
	for (int i=2; i<=n; i++) G[par2[0][i]].pb(i);
	timer=1;
	dfs1(1, stt2, fnt2);
	
	for (int j=1; j<LOG; j++) for (int i=1; i<=n; i++){
		par1[j][i]=par1[j-1][par1[j-1][i]];
		par2[j][i]=par2[j-1][par2[j-1][i]];
	}

	for (int i=1; i<=n; i++) Add(1, 1, n+1, stt1[i], stt2[i]);
	for (int i=1; i<4*MAXN; i++) sort(all(seg[i])), seg[i].pb(inf);

	m=SZ(S);
	vi out(m, 0);
	for (int i=0; i<m; i++) out[i]=Solve(S[i]+1, E[i]+1, L[i]+1, R[i]+1);
	return out;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4


6 6 1
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2


*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 73368 KB Output is correct
2 Correct 95 ms 73300 KB Output is correct
3 Correct 80 ms 73232 KB Output is correct
4 Correct 82 ms 73336 KB Output is correct
5 Correct 82 ms 73284 KB Output is correct
6 Correct 81 ms 73280 KB Output is correct
7 Correct 82 ms 73308 KB Output is correct
8 Correct 81 ms 73328 KB Output is correct
9 Correct 82 ms 73288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 73368 KB Output is correct
2 Correct 95 ms 73300 KB Output is correct
3 Correct 80 ms 73232 KB Output is correct
4 Correct 82 ms 73336 KB Output is correct
5 Correct 82 ms 73284 KB Output is correct
6 Correct 81 ms 73280 KB Output is correct
7 Correct 82 ms 73308 KB Output is correct
8 Correct 81 ms 73328 KB Output is correct
9 Correct 82 ms 73288 KB Output is correct
10 Correct 109 ms 74252 KB Output is correct
11 Correct 92 ms 74180 KB Output is correct
12 Correct 89 ms 74088 KB Output is correct
13 Correct 91 ms 74272 KB Output is correct
14 Correct 91 ms 74308 KB Output is correct
15 Correct 91 ms 74272 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 136248 KB Output is correct
2 Correct 1689 ms 139604 KB Output is correct
3 Correct 1643 ms 137320 KB Output is correct
4 Correct 1686 ms 136288 KB Output is correct
5 Correct 1676 ms 136252 KB Output is correct
6 Correct 1642 ms 136280 KB Output is correct
7 Correct 1583 ms 136380 KB Output is correct
8 Correct 1563 ms 139500 KB Output is correct
9 Correct 1266 ms 137332 KB Output is correct
10 Correct 905 ms 136328 KB Output is correct
11 Correct 999 ms 136316 KB Output is correct
12 Correct 1169 ms 136204 KB Output is correct
13 Correct 1558 ms 140908 KB Output is correct
14 Correct 1613 ms 140888 KB Output is correct
15 Correct 1613 ms 140872 KB Output is correct
16 Correct 1567 ms 140744 KB Output is correct
17 Correct 1649 ms 136288 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 73368 KB Output is correct
2 Correct 95 ms 73300 KB Output is correct
3 Correct 80 ms 73232 KB Output is correct
4 Correct 82 ms 73336 KB Output is correct
5 Correct 82 ms 73284 KB Output is correct
6 Correct 81 ms 73280 KB Output is correct
7 Correct 82 ms 73308 KB Output is correct
8 Correct 81 ms 73328 KB Output is correct
9 Correct 82 ms 73288 KB Output is correct
10 Correct 109 ms 74252 KB Output is correct
11 Correct 92 ms 74180 KB Output is correct
12 Correct 89 ms 74088 KB Output is correct
13 Correct 91 ms 74272 KB Output is correct
14 Correct 91 ms 74308 KB Output is correct
15 Correct 91 ms 74272 KB Output is correct
16 Correct 1699 ms 136248 KB Output is correct
17 Correct 1689 ms 139604 KB Output is correct
18 Correct 1643 ms 137320 KB Output is correct
19 Correct 1686 ms 136288 KB Output is correct
20 Correct 1676 ms 136252 KB Output is correct
21 Correct 1642 ms 136280 KB Output is correct
22 Correct 1583 ms 136380 KB Output is correct
23 Correct 1563 ms 139500 KB Output is correct
24 Correct 1266 ms 137332 KB Output is correct
25 Correct 905 ms 136328 KB Output is correct
26 Correct 999 ms 136316 KB Output is correct
27 Correct 1169 ms 136204 KB Output is correct
28 Correct 1558 ms 140908 KB Output is correct
29 Correct 1613 ms 140888 KB Output is correct
30 Correct 1613 ms 140872 KB Output is correct
31 Correct 1567 ms 140744 KB Output is correct
32 Correct 1649 ms 136288 KB Output is correct
33 Correct 1796 ms 137228 KB Output is correct
34 Correct 484 ms 92692 KB Output is correct
35 Correct 1830 ms 139444 KB Output is correct
36 Correct 1834 ms 136696 KB Output is correct
37 Correct 1959 ms 138748 KB Output is correct
38 Correct 1809 ms 137168 KB Output is correct
39 Correct 1708 ms 145804 KB Output is correct
40 Correct 1461 ms 142524 KB Output is correct
41 Correct 1371 ms 138300 KB Output is correct
42 Correct 1119 ms 136824 KB Output is correct
43 Correct 1742 ms 142128 KB Output is correct
44 Correct 1669 ms 138736 KB Output is correct
45 Correct 1236 ms 146032 KB Output is correct
46 Correct 1255 ms 145816 KB Output is correct
47 Correct 1607 ms 140920 KB Output is correct
48 Correct 1537 ms 140836 KB Output is correct
49 Correct 1553 ms 141012 KB Output is correct
50 Correct 1513 ms 140932 KB Output is correct
51 Correct 1209 ms 142888 KB Output is correct
52 Correct 1289 ms 142920 KB Output is correct