oj.uz

Submission #1060022

# Submission time Handle Problem Language Result Execution time Memory
1060022 2024-08-15T10:08:37 Z ReLice Werewolf (IOI18_werewolf) C++17
34 / 100
 499 ms 100316 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(true){
			
			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
			if(inc){
				i++;
				if(i >= n) break;
			}else{
				i--;
				if(i < 0) break;
			}
		}
	}
	
	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 9 ms 9888 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 9 ms 9888 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 499 ms 83060 KB Output is correct
2 Correct 421 ms 81116 KB Output is correct
3 Correct 445 ms 79220 KB Output is correct
4 Correct 474 ms 79352 KB Output is correct
5 Correct 418 ms 80092 KB Output is correct
6 Correct 427 ms 81524 KB Output is correct
7 Correct 396 ms 82940 KB Output is correct
8 Correct 397 ms 81140 KB Output is correct
9 Correct 357 ms 79196 KB Output is correct
10 Correct 413 ms 78836 KB Output is correct
11 Correct 408 ms 78840 KB Output is correct
12 Correct 454 ms 79972 KB Output is correct
13 Correct 391 ms 100200 KB Output is correct
14 Correct 385 ms 100260 KB Output is correct
15 Correct 349 ms 100204 KB Output is correct
16 Correct 362 ms 100316 KB Output is correct
17 Correct 402 ms 83084 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 9 ms 9888 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -