oj.uz

Submission #421561

# Submission time Handle Problem Language Result Execution time Memory
421561 2021-06-09T09:06:41 Z alishahali1382 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 56012 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];

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;
}
bool Solve(int y, int x, int l, int r){ // go from y to x
	// debug2(x, y)
	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];
	// debug2(x, y)
	// debug2(stt1[x], fnt1[x])
	// debug2(stt2[y], fnt2[y])
	for (int i=l; i<=r; i++)
		if (stt1[x]<=stt1[i] && stt1[i]<fnt1[x] && stt2[y]<=stt2[i] && stt2[i]<fnt2[y]) return 1;
	return 0;
}

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]];
	}

	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 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 6 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7600 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 6 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7600 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 15 ms 8268 KB Output is correct
11 Correct 17 ms 8356 KB Output is correct
12 Correct 26 ms 8324 KB Output is correct
13 Correct 13 ms 8460 KB Output is correct
14 Correct 14 ms 8440 KB Output is correct
15 Correct 33 ms 8428 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4082 ms 56012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 6 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7600 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 15 ms 8268 KB Output is correct
11 Correct 17 ms 8356 KB Output is correct
12 Correct 26 ms 8324 KB Output is correct
13 Correct 13 ms 8460 KB Output is correct
14 Correct 14 ms 8440 KB Output is correct
15 Correct 33 ms 8428 KB Output is correct
16 Execution timed out 4082 ms 56012 KB Time limit exceeded
17 Halted 0 ms 0 KB -