oj.uz

Submission #1047180

# Submission time Handle Problem Language Result Execution time Memory
1047180 2024-08-07T10:04:38 Z Alihan_8 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 63488 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define ln '\n'

struct Dsu{
	vector <int> fa, _in, _out, euler;
	
	vector <vector<int>> adj;
	
	bool isMax;
	
	Dsu(int n, bool isMax) : isMax(isMax) {
		fa.resize(n);
		iota(all(fa), 0);
		
		adj.resize(n);
		_in.resize(n);
		_out.resize(n);
	}
	
	int get(int u){
		return u ^ fa[u] ? fa[u] = get(fa[u]) : u;
	}
	
	bool f(int u, int v){
		return isMax ? u > v : u < v;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		if ( !f(u, v) ) swap(u, v);
		
		fa[v] = u; 
		adj[u].pb(v);
		
		return true;
	}
	
	void RunDfs(){
		int ct = -1;
		
		auto dfs = [&](auto dfs, int u) -> void{
			_in[u] = ++ct;
			euler.pb(u);
			
			for ( auto &v: adj[u] ){
				//~ cout << u << " " << v << ln;
				
				dfs(dfs, v);
			} _out[u] = ct;
		};
		
		int root = get(0);
		
		dfs(dfs, root);
	}
};

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 n = N, m = X.size(), q = S.size();
	
	// Subtask #3
	
	vector <vector<int>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	
	Dsu ds(n, 0), de(n, 1);
	
	vector <int> ps(q), pe(q);

	{ // for S[i]
		vector <vector<int>> qu(n);
		
		for ( int i = 0; i < q; i++ ){
			qu[L[i]].pb(i);
		}
		
		for ( int u = n - 1; u >= 0; u-- ){
			for ( auto &v: adj[u] ){
				if ( v > u ){
					ds.merge(u, v);
				}
			}
			
			for ( auto &j: qu[u] ){
				ps[j] = ds.get(S[j]);
			}
		}
	}
	{ // for E[i]
		vector <vector<int>> qu(n);
		
		for ( int i = 0; i < q; i++ ){
			qu[R[i]].pb(i);
		}
		
		for ( int u = 0; u < n; u++ ){
			for ( auto &v: adj[u] ){
				if ( v < u ){
					de.merge(u, v);
				}
			}
			
			for ( auto &j: qu[u] ){
				pe[j] = de.get(E[j]);
			}
		}
	}
	
	ds.RunDfs(); 
	de.RunDfs(); 
	
	vector <int> ans(q);
	
	for ( int i = 0; i < q; i++ ){
		for ( int j = ds._in[ps[i]]; j <= ds._out[ps[i]]; j++ ){ // subtree of pe[i]
			for ( int k = de._in[pe[i]]; k <= de._out[pe[i]]; k++ ){ // subtree of pe[i]
				if ( ds.euler[j] == de.euler[k] ){
					ans[i] = 1;
				}
			}
		}
	}
	
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2974 ms 1336 KB Output is correct
11 Correct 1481 ms 1308 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 2547 ms 1420 KB Output is correct
14 Correct 129 ms 1408 KB Output is correct
15 Correct 1624 ms 1368 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2840 ms 60932 KB Output is correct
2 Execution timed out 4054 ms 63488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2974 ms 1336 KB Output is correct
11 Correct 1481 ms 1308 KB Output is correct
12 Correct 7 ms 1116 KB Output is correct
13 Correct 2547 ms 1420 KB Output is correct
14 Correct 129 ms 1408 KB Output is correct
15 Correct 1624 ms 1368 KB Output is correct
16 Correct 2840 ms 60932 KB Output is correct
17 Execution timed out 4054 ms 63488 KB Time limit exceeded
18 Halted 0 ms 0 KB -