oj.uz

Submission #1042033

# Submission time Handle Problem Language Result Execution time Memory
1042033 2024-08-02T12:50:40 Z Dan4Life Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 92076 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar2 = array<int,2>;
const int mxN = (int)2e5+10;
const int mxLg = 20;
int n,m,q,dfs_timer;
int jmp[2][mxLg][mxN];
int st[2][mxN], en[2][mxN], A[2][mxN];
vector<int> adj[mxN], euler[2], adj2[2][mxN];

template<int SZ> struct DSU{
    int p[SZ], root;
    void init(int n){ for(int i=0; i<n; i++) p[i]=i;}
    int findSet(int i){return p[i]==i?i:p[i]=findSet(p[i]);}
    bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
    void unionSet(int t, int i, int j){
        int x = findSet(i), y = findSet(j);
        if(x==y) return;
        adj2[t][x].pb(y); root=x, p[y]=x;
    }
};
DSU<mxN> dsu[2];

void dfs(int s, int p, int t){
	st[t][s] = dfs_timer++;
	euler[t].pb(s); jmp[t][0][s] = p;
	for(auto u : adj2[t][s]){
		if(u==p) continue;
		dfs(u,s,t);
	}
	en[t][s] = dfs_timer-1;
}

vi check_validity(int _N, vi U, vi V, vi S, vi T, vi L, vi R) {
	n = _N, m = sz(U), q = sz(S);
	vi ans(q,0); memset(jmp,-1,sizeof(jmp));
	dsu[0].init(n), dsu[1].init(n);
	for(int i = 0; i < m; i++){
		int a = U[i], b = V[i];
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = n-1; i >= 0; i--)
		for(auto u : adj[i]) if(u>i) 
			dsu[0].unionSet(0,i,u);
	for(int i = 0; i < n; i++)
		for(auto u : adj[i]) if(u<i) 
			dsu[1].unionSet(1,i,u);
	for(int t : {0,1}){
		dfs_timer = 0; dfs(dsu[t].root, -1, t);
		for(int i = 1; i < mxLg; i++)
			for(int j = 0; j < n; j++)
				jmp[t][i][j] = jmp[t][i-1][jmp[t][i-1][j]];
	}
	for(int i = 0; i < q; i++){
		int s = S[i], t = T[i], l = L[i], r = R[i];
		for(int j = mxLg-1; j>=0; j--){
			if(jmp[0][j][s]!=-1 and jmp[0][j][s]>=l) s = jmp[0][j][s];
			if(jmp[1][j][t]!=-1 and jmp[1][j][t]<=r) t = jmp[1][j][t];
		}
		for(int j = st[0][s]; j <= en[0][s]; j++){
			for(int k = st[1][t]; k <= en[1][t]; k++){
				ans[i]|=(euler[0][j]==euler[1][k]);
			}
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51800 KB Output is correct
2 Correct 7 ms 51932 KB Output is correct
3 Correct 6 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 7 ms 51960 KB Output is correct
6 Correct 7 ms 51804 KB Output is correct
7 Correct 6 ms 51804 KB Output is correct
8 Correct 6 ms 51804 KB Output is correct
9 Correct 6 ms 51960 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51800 KB Output is correct
2 Correct 7 ms 51932 KB Output is correct
3 Correct 6 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 7 ms 51960 KB Output is correct
6 Correct 7 ms 51804 KB Output is correct
7 Correct 6 ms 51804 KB Output is correct
8 Correct 6 ms 51804 KB Output is correct
9 Correct 6 ms 51960 KB Output is correct
10 Correct 2969 ms 52508 KB Output is correct
11 Correct 1485 ms 52312 KB Output is correct
12 Correct 12 ms 52312 KB Output is correct
13 Correct 2477 ms 52664 KB Output is correct
14 Correct 135 ms 52568 KB Output is correct
15 Correct 1561 ms 52572 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2772 ms 87496 KB Output is correct
2 Execution timed out 4065 ms 92076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51800 KB Output is correct
2 Correct 7 ms 51932 KB Output is correct
3 Correct 6 ms 51804 KB Output is correct
4 Correct 6 ms 51804 KB Output is correct
5 Correct 7 ms 51960 KB Output is correct
6 Correct 7 ms 51804 KB Output is correct
7 Correct 6 ms 51804 KB Output is correct
8 Correct 6 ms 51804 KB Output is correct
9 Correct 6 ms 51960 KB Output is correct
10 Correct 2969 ms 52508 KB Output is correct
11 Correct 1485 ms 52312 KB Output is correct
12 Correct 12 ms 52312 KB Output is correct
13 Correct 2477 ms 52664 KB Output is correct
14 Correct 135 ms 52568 KB Output is correct
15 Correct 1561 ms 52572 KB Output is correct
16 Correct 2772 ms 87496 KB Output is correct
17 Execution timed out 4065 ms 92076 KB Time limit exceeded
18 Halted 0 ms 0 KB -