oj.uz

Submission #773189

# Submission time Handle Problem Language Result Execution time Memory
773189 2023-07-04T16:24:29 Z amunduzbaev Werewolf (IOI18_werewolf) C++17
34 / 100
 521 ms 97668 KB 
#include "werewolf.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll

const int N = 2e5 + 5;

struct ST{
	int tree[N << 2];
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r){
			return tree[x];
		}
		
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree;

const int M = 18;
vector<int> qwe[N], edges[2][N];
int tin[2][N], tout[2][N];
int par[2][N][M];

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
	int m = x.size(), q = s.size();
	for(int i=0;i<m;i++){
		qwe[x[i]].push_back(y[i]);
		qwe[y[i]].push_back(x[i]);
	}
	
	{ // building trees
		vector<int> par(n), sz(n, 1), root(n);
		iota(par.begin(), par.end(), 0);
		iota(root.begin(), root.end(), 0);
		
		function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
		auto merge = [&](int a, int b, int r){
			a = f(a), b = f(b);
			if(a == b) return;
			if(sz[a] < sz[b]) swap(a, b);
			par[b] = a;
			root[a] = r;
			sz[a] += sz[b];
		};
		
		for(int i=n - 1;~i;i--){
			for(auto x : qwe[i]){
				if(x > i && root[f(x)] != i){
					edges[0][i].push_back(root[f(x)]);
					merge(x, i, i);
				}
			}
		}
		
		iota(par.begin(), par.end(), 0);
		iota(root.begin(), root.end(), 0);
		fill(sz.begin(), sz.end(), 1);
		
		for(int i=0;i<n;i++){
			for(auto x : qwe[i]){
				if(x < i && root[f(x)] != i){
					edges[1][i].push_back(root[f(x)]);
					merge(x, i, i);
				}
			}
		}
	}
	
	//~ for(int t=0;t<2;t++){
		//~ for(int i=0;i<n;i++){
			//~ for(auto x : edges[t][i]){
				//~ cout<<t<<" "<<i<<" "<<x<<"\n";
			//~ }
		//~ }
		
		//~ cout<<"\n";
	//~ }
	
	ar<int, 2> root = {0, n - 1};

	for(int t=0;t<2;t++){
		int t_ = 0;
		function<void(int)> dfs = [&](int u){
			for(int j=1;j<M;j++){
				par[t][u][j] = par[t][par[t][u][j - 1]][j - 1];
			}
			tin[t][u] = ++t_;
			for(auto x : edges[t][u]){
				par[t][x][0] = u;
				dfs(x);
			}
			tout[t][u] = t_;
		};
		
		par[t][root[t]][0] = root[t];
		dfs(root[t]);
	}
	
	vector<ar<int, 2>> ver(n);
	
	auto get = [&](int t, int u, int l, int r){
		for(int j=M - 1;~j;j--){
			if(l <= par[t][u][j] && par[t][u][j] <= r){
				u = par[t][u][j];
			}
		}
		
		return u;
	};
	
	for(int i=0;i<q;i++){
		ver[i][0] = get(0, s[i], l[i], n);
		ver[i][1] = get(1, e[i], 0, r[i]);
	}
	
	vector<int> p(q);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return tout[0][ver[i][0]] < tout[0][ver[j][0]];
	});
	
	vector<int> tot(n);
	iota(tot.begin(), tot.end(), 0);
	sort(tot.begin(), tot.end(), [&](int i, int j){
		return tout[0][i] < tout[0][j];
	});
	
	vector<int> res(q);
	int j = 0;
	for(auto i : p){
		while(j < n && tin[0][tot[j]] <= tout[0][ver[i][0]]){
			tree.set(tin[1][tot[j]], tin[0][tot[j]]);
			j++;
		}
		
		if(tree.get(tin[1][ver[i][1]], tout[1][ver[i][1]]) >= tin[0][ver[i][0]]){
			res[i] = 1;
		}
	}
	
	return res;
}

/*

6 6 3
5 1
1 2
1 3
3 4
3 0
2 5
4 2 1 2
4 2 2 2
5 4 3 4

5 4 4
4 1
1 0
0 3
3 2
4 0 1 1 
4 3 1 3
2 0 1 1
3 1 3 3

*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Runtime error 18 ms 28996 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Runtime error 18 ms 28996 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 84040 KB Output is correct
2 Correct 467 ms 90976 KB Output is correct
3 Correct 430 ms 86396 KB Output is correct
4 Correct 416 ms 84496 KB Output is correct
5 Correct 436 ms 84420 KB Output is correct
6 Correct 443 ms 84128 KB Output is correct
7 Correct 506 ms 83992 KB Output is correct
8 Correct 396 ms 91112 KB Output is correct
9 Correct 356 ms 86396 KB Output is correct
10 Correct 346 ms 84444 KB Output is correct
11 Correct 370 ms 84264 KB Output is correct
12 Correct 392 ms 84304 KB Output is correct
13 Correct 463 ms 97660 KB Output is correct
14 Correct 442 ms 97576 KB Output is correct
15 Correct 455 ms 97636 KB Output is correct
16 Correct 467 ms 97668 KB Output is correct
17 Correct 468 ms 83992 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Runtime error 18 ms 28996 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -