oj.uz

Submission #926508

# Submission time Handle Problem Language Result Execution time Memory
926508 2024-02-13T07:33:46 Z GrindMachine Split the Attractions (IOI19_split) C++17
22 / 100
 618 ms 1048576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "split.h"

vector<int> adj[N];
vector<int> subsiz(N);
vector<int> par(N);

void dfs1(int u, int p){
	subsiz[u] = 1;
	par[u] = p;
	trav(v,adj[u]){
		if(v == p) conts;
		dfs1(v,u);
		subsiz[u] += subsiz[v];
	}
}

pii to_col;
vector<int> ans;

void dfs2(int u, int p){
	if(!to_col.ss) return;
	to_col.ss--;
	ans[u] = to_col.ff;

	trav(v,adj[u]){
		if(v == p) conts;
		if(ans[v]) conts;
		dfs2(v,u);
	}
}

vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
	rep(i,sz(p)){
		int u = p[i], v = q[i];
		adj[u].pb(v), adj[v].pb(u);
	}

	dfs1(0,-1);
	ans.resize(n);

	rep(u,n){
		int s = subsiz[u];
		
		if(s >= A and n-s >= min(B,C)){
			to_col = {1,A};
			dfs2(u,par[u]);

			if(B < C){
				to_col = {2,B};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 3;
					}
				}
			}
			else{
				to_col = {3,C};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 2;
					}
				}
			}

			return ans;
		}
		
		if(s >= B and n-s >= min(A,C)){
			to_col = {2,B};
			dfs2(u,par[u]);

			if(A < C){
				to_col = {1,A};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 3;
					}
				}
			}
			else{
				to_col = {3,C};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 1;
					}
				}
			}

			return ans;
		}

		if(s >= C and n-s >= min(A,B)){
			to_col = {1,C};
			dfs2(u,par[u]);

			if(A < B){
				to_col = {1,A};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 2;
					}
				}
			}
			else{
				to_col = {2,B};
				dfs2(0,-1);
				rep(i,n){
					if(!ans[i]){
						ans[i] = 1;
					}
				}
			}

			return ans;
		}
	}

	return vector<int>(n,0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB ok, correct split
2 Runtime error 618 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB ok, correct split
2 Runtime error 593 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB ok, correct split
2 Correct 36 ms 10248 KB ok, correct split
3 Correct 15 ms 6248 KB ok, correct split
4 Correct 1 ms 3420 KB ok, correct split
5 Correct 38 ms 11624 KB ok, correct split
6 Correct 55 ms 11384 KB ok, correct split
7 Correct 47 ms 11492 KB ok, correct split
8 Correct 49 ms 12248 KB ok, correct split
9 Correct 47 ms 11484 KB ok, correct split
10 Correct 16 ms 5724 KB ok, no valid answer
11 Correct 18 ms 6748 KB ok, no valid answer
12 Correct 34 ms 10460 KB ok, no valid answer
13 Correct 34 ms 10332 KB ok, no valid answer
14 Correct 31 ms 10444 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 579 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB ok, correct split
2 Runtime error 618 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -