oj.uz

Submission #294718

# Submission time Handle Problem Language Result Execution time Memory
294718 2020-09-09T08:49:47 Z _7_7_ Split the Attractions (IOI19_split) C++14
11 / 100
 174 ms 15608 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, par[N];
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];
			par[v] = to;
		}

	tout[v] = timer;
}


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


bool check (int v) {
	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] >= a)
			T = min(T, mp(n - cnt[i], mp(i, 1)));
	}

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

	return res;
}

Subtask #1
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 Incorrect 115 ms 15336 KB invalid split: #1=66666, #2=33333, #3=1
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 3 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 129 ms 14712 KB ok, correct split
5 Correct 102 ms 10916 KB ok, correct split
6 Correct 106 ms 15608 KB ok, correct split
7 Correct 116 ms 13956 KB ok, correct split
8 Correct 174 ms 14320 KB ok, correct split
9 Correct 114 ms 10872 KB ok, correct split
10 Correct 71 ms 10608 KB ok, correct split
11 Correct 67 ms 10480 KB ok, correct split
12 Correct 71 ms 10864 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Incorrect 95 ms 11000 KB invalid split: #1=1, #2=40000, #3=59999
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 Incorrect 4 ms 2944 KB invalid split: #1=1, #2=10, #3=2010
10 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 Incorrect 115 ms 15336 KB invalid split: #1=66666, #2=33333, #3=1
8 Halted 0 ms 0 KB -