oj.uz

Submission #1060034

# Submission time Handle Problem Language Result Execution time Memory
1060034 2024-08-15T10:11:55 Z ReLice Werewolf (IOI18_werewolf) C++17
34 / 100
 404 ms 91956 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define ins insert
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N=2e5+5;
const ll inf=1e9;
vector<vll> G(N);
struct dsu{
	vector<vll> g;
	vll tin, tout;
	vll p, pr;
	ll tiktak;
	ll n;
	bool inc;
	
	dsu(ll N, ll f){
		n = N;
		inc = f;
		tiktak = -1;
		
		tin.resize(n);
		tout.resize(n);
		pr.resize(n);
		g.resize(n);
		p.resize(n);
		
		for(ll i=0;i<n;i++) p[i] = i;
	}
	
	ll anc(ll a){
		return (p[a] == a ? a : p[a] = anc(p[a]));
	}
	
	bool f(ll a, ll b){
		return inc ? a < b : a > b;
	}
	
	bool uni(ll a, ll b){
		a = anc(a), b = anc(b);
		
		if(a == b) return false;
		
		if(f(a, b)) swap(a, b);
		
		p[b] = a;
		g[a].pb(b);
		
		return true;
	}
	
	void build(vll s, vll l){
		ll i, q = s.size();
		
		vector<vll> qu(n);
		
		for(i=0;i<q;i++){
			qu[l[i]].pb(i);
		}
		
		if(inc) i = 0;
		else i = n - 1;
		while(i>=0 && i<n){
			for(auto to : G[i]){
				if((inc && to < i ) || (!inc && to > i)){
					uni(to, i);
				}
			}
			
			for(auto j : qu[i]){
				pr[j] = anc(s[j]);
			}
			
			//iteration
			i += inc ? 1 : -1;
		}
	}
	
	void dfs(ll v){
		tin[v] = ++tiktak;
		
		for(auto i : g[v]) dfs(i);
		
		tout[v] = tiktak;
	}
};

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	ll i;
	ll m = X.size();
	ll q = S.size();
	
	for(i=0;i<m;i++){
		G[X[i]].pb(Y[i]);
		G[Y[i]].pb(X[i]);
	}
	
	dsu s(n, 0);
	dsu t(n, 1);
	
	s.build(S, L);
	t.build(E, R);
	
	s.dfs(0);
	t.dfs(n-1);
	
	vector<vll> qu(n);
	for(i=0;i<q;i++){
		qu[s.pr[i]].pb(i);
	}
	
	vll ans(q);
	vector<set<ll>> st(n);
	
	function<void(int)> dfs = [&](ll v){
		st[v].ins(t.tin[v]);
		for(auto i : s.g[v]){
			dfs(i);
			
			if(st[v].size() < st[i].size()) swap(st[i], st[v]);
			
			for(auto j : st[i]){
				st[v].ins(j);
			}st[i].clear();
		}
		
		for(auto i : qu[v]){
			int l = t.tin[t.pr[i]], r = t.tout[t.pr[i]];
			
			ans[i] = (st[v].lb(l) != st[v].ub(r));
		}
	};
	
	dfs(0);
	
	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 5 ms 10076 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 5 ms 10076 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 74480 KB Output is correct
2 Correct 384 ms 72668 KB Output is correct
3 Correct 385 ms 70908 KB Output is correct
4 Correct 392 ms 70880 KB Output is correct
5 Correct 382 ms 71640 KB Output is correct
6 Correct 386 ms 72964 KB Output is correct
7 Correct 387 ms 74488 KB Output is correct
8 Correct 360 ms 72672 KB Output is correct
9 Correct 342 ms 70980 KB Output is correct
10 Correct 322 ms 70648 KB Output is correct
11 Correct 370 ms 70632 KB Output is correct
12 Correct 344 ms 71644 KB Output is correct
13 Correct 354 ms 91956 KB Output is correct
14 Correct 365 ms 91648 KB Output is correct
15 Correct 380 ms 91628 KB Output is correct
16 Correct 345 ms 91892 KB Output is correct
17 Correct 368 ms 74504 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 5 ms 10076 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -