oj.uz

Submission #1060044

# Submission time Handle Problem Language Result Execution time Memory
1060044 2024-08-15T10:16:10 Z ReLice Werewolf (IOI18_werewolf) C++17
34 / 100
 441 ms 91868 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] = pr[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 1 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 4 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 1 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 4 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 398 ms 74500 KB Output is correct
2 Correct 411 ms 72684 KB Output is correct
3 Correct 441 ms 70872 KB Output is correct
4 Correct 432 ms 71064 KB Output is correct
5 Correct 414 ms 71676 KB Output is correct
6 Correct 387 ms 73180 KB Output is correct
7 Correct 389 ms 74500 KB Output is correct
8 Correct 381 ms 72668 KB Output is correct
9 Correct 362 ms 70860 KB Output is correct
10 Correct 331 ms 70620 KB Output is correct
11 Correct 355 ms 70492 KB Output is correct
12 Correct 377 ms 71644 KB Output is correct
13 Correct 355 ms 91652 KB Output is correct
14 Correct 351 ms 91868 KB Output is correct
15 Correct 425 ms 91632 KB Output is correct
16 Correct 368 ms 91644 KB Output is correct
17 Correct 380 ms 74512 KB Output is correct

Subtask #4
0 / 51.0

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