oj.uz

Submission #294701

# Submission time Handle Problem Language Result Execution time Memory
294701 2020-09-09T08:38:17 Z _7_7_ Split the Attractions (IOI19_split) C++14
7 / 100
 121 ms 23928 KB 
#include "split.h"
#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;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 1e5 + 112;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;

using namespace std;

int n, m, cnt[N], tin[N], tout[N], timer;
pair < int, pii > T;
vi g[N], res;

void dfs (int v) {
	tin[v] = ++timer;
	cnt[v] = 1;
	for (auto to : g[v])
		if (!cnt[to]) {
			dfs(to);   
			cnt[v] += cnt[to];
		}

	tout[v] = timer;
}


bool upper (int v, int u) {
	return tin[v] <= tin[u] && tout[u] <= tout[v];
}


bool check (int v) {
	if (v == T.s.f)
		return 0;

	if ((!T.s.s && upper(T.s.f, v)) || (T.s.s && !upper(T.s.f, v)))
		return 0;
	return 1;
}

void dfs1 (int v, int c, int &x) {
	if (!x)
		return;

	--x;			
	res[v] = c;
	for (auto to : g[v])
		if (check(to) && !res[to]) 
			dfs1(to, c, x);		
}

void dfs2 (int v, int c, int &x) {
	if (!x)
		return;
	--x;
	res[v] = c;
	for (auto to : g[v])
		if (!check(to) && !res[to])
			dfs2(to, c, x);
}



vi find_split(int _n, int a, int b, int c, vi p, vi q) {
	n = _n;
	m = sz(p);
	for (int i = 0; i < m; ++i) {
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
		
	res.resize(n, 0);
	dfs(0);
	
	T = {inf, {inf, inf}};
	
	int A = 1, B = 2, C = 3;
	if (a > b && a > c) {
	    swap(A, C);
		swap(a, c);      
	}
	
	if (b > a && b > c) {
		swap(b, c);      
		swap(B, C);
	}

	if (a > b) {
		swap(a, b);
		swap(A, B);
	}

	for (int i = 0; i < n; ++i) {
		if (cnt[i] >= a)
			T = min(T, mp(cnt[i], mp(i, 0)));
		if (n - cnt[i] + 1 >= a)
			T = min(T, mp(n - cnt[i] + 1, mp(i, 1)));
	}

	if (n - T.f < b)  
		return res;	
			
	int root = 0;
	while (!check(root))
		++root;
	dfs1(root, B, b);
	dfs2(T.s.f, A, a);
	assert(!a && !b);
	
	for (int i = 0; i < n; ++i)
		if (!res[i])
			res[i] = C;

	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 107 ms 13820 KB ok, correct split
8 Correct 95 ms 12408 KB ok, correct split
9 Correct 116 ms 12024 KB ok, correct split
10 Correct 95 ms 14072 KB ok, correct split
11 Correct 110 ms 13944 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 121 ms 12536 KB ok, correct split
5 Correct 86 ms 9464 KB ok, correct split
6 Correct 92 ms 14072 KB ok, correct split
7 Runtime error 97 ms 23928 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB ok, correct split
2 Runtime error 86 ms 18168 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, no valid answer
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 2 ms 2688 KB ok, correct split
8 Correct 2 ms 2688 KB ok, correct split
9 Correct 4 ms 2976 KB ok, correct split
10 Correct 4 ms 2944 KB ok, correct split
11 Correct 2 ms 2688 KB ok, correct split
12 Correct 4 ms 2944 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Runtime error 6 ms 5248 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 107 ms 13820 KB ok, correct split
8 Correct 95 ms 12408 KB ok, correct split
9 Correct 116 ms 12024 KB ok, correct split
10 Correct 95 ms 14072 KB ok, correct split
11 Correct 110 ms 13944 KB ok, correct split
12 Correct 2 ms 2688 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 121 ms 12536 KB ok, correct split
16 Correct 86 ms 9464 KB ok, correct split
17 Correct 92 ms 14072 KB ok, correct split
18 Runtime error 97 ms 23928 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -