oj.uz

Submission #293788

# Submission time Handle Problem Language Result Execution time Memory
293788 2020-09-08T12:07:41 Z egekabas Split the Attractions (IOI19_split) C++14
40 / 100
 143 ms 15608 KB 
#include "split.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
using namespace std;
vector<pii> col;
vector<int> ans;
int sz[100009];
vector<int> g[100009];
void calcsz(int v, int prt){
	sz[v] = 1;
	for(auto u : g[v])
		if(u != prt){
			calcsz(u, v);
			sz[v] += sz[u];
		}
}
int lft, use;
void paint(int v, int prt){
	if(lft <= 0) return;
	ans[v] = use;
	--lft;
	for(auto u : g[v])
		if(u != prt){
			paint(u, v);
		}
}
int ok = 0;
int N;
void dfs(int v, int prt){
	if(ok) return;
	for(auto u : g[v]){
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
		swap(col[0], col[1]);
		if(sz[u] >= col[0].ff && N-sz[u] >= col[1].ff){
			ok = 1;
			lft = col[0].ff;
			use = col[0].ss;
			paint(u, v);
			lft = col[1].ff;
			use = col[1].ss;
			paint(v, u);
			return;
		}
	}
	for(auto u : g[v]){
		if(u == prt) continue;
		int vbef = sz[v];
		int ubef = sz[u];
		sz[v] -= sz[u];
		sz[u] += sz[v];
		dfs(u, v);
		sz[v] = vbef;
		sz[u] = ubef;
	}
}
void dfssp(int v){
	if(lft <= 0) return;
	--lft;
	ans[v] = use;
	for(auto u : g[v])
		if(ans[u] == 0)
			dfssp(u);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	ans.resize(n);
	for(int i = 0; i < p.size(); ++i){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	if(p.size() != n-1){
		lft = b; use = 2;
		dfssp(0);
		for(int i = 0; i < n; ++i)
			if(ans[i] == 0){
				lft = a;
				use = 1;
				dfssp(i);
				break;
			}
		for(int i = 0; i < n; ++i)
			if(ans[i] == 0){
				ans[i] = 3;
			}
		return ans;
	}
	col = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(col));
	
	calcsz(0, -1);
	dfs(0, -1);
	if(ok == 0) return ans;
	for(auto &u : ans)
		if(u == 0)
			u = col[2].ss;
	return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i = 0; i < p.size(); ++i){
      |                 ~~^~~~~~~~~~
split.cpp:92:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  if(p.size() != n-1){
      |     ~~~~~~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 112 ms 15608 KB ok, correct split
8 Correct 107 ms 13920 KB ok, correct split
9 Correct 94 ms 13304 KB ok, correct split
10 Correct 78 ms 9264 KB ok, correct split
11 Correct 86 ms 10360 KB ok, correct split

Subtask #2
11.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 106 ms 10872 KB ok, correct split
5 Correct 110 ms 9848 KB ok, correct split
6 Correct 78 ms 9336 KB ok, correct split
7 Correct 106 ms 13688 KB ok, correct split
8 Correct 143 ms 12024 KB ok, correct split
9 Correct 88 ms 9464 KB ok, correct split
10 Correct 61 ms 9712 KB ok, correct split
11 Correct 63 ms 9712 KB ok, correct split
12 Correct 71 ms 10096 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 84 ms 8696 KB ok, correct split
3 Correct 28 ms 5120 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 101 ms 10616 KB ok, correct split
6 Correct 96 ms 10488 KB ok, correct split
7 Correct 102 ms 10744 KB ok, correct split
8 Correct 102 ms 11384 KB ok, correct split
9 Correct 106 ms 10616 KB ok, correct split
10 Correct 25 ms 4608 KB ok, no valid answer
11 Correct 39 ms 5632 KB ok, no valid answer
12 Correct 75 ms 8820 KB ok, no valid answer
13 Correct 88 ms 8696 KB ok, no valid answer
14 Correct 62 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB invalid split: #1=1, #2=2, #3=6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 112 ms 15608 KB ok, correct split
8 Correct 107 ms 13920 KB ok, correct split
9 Correct 94 ms 13304 KB ok, correct split
10 Correct 78 ms 9264 KB ok, correct split
11 Correct 86 ms 10360 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 106 ms 10872 KB ok, correct split
16 Correct 110 ms 9848 KB ok, correct split
17 Correct 78 ms 9336 KB ok, correct split
18 Correct 106 ms 13688 KB ok, correct split
19 Correct 143 ms 12024 KB ok, correct split
20 Correct 88 ms 9464 KB ok, correct split
21 Correct 61 ms 9712 KB ok, correct split
22 Correct 63 ms 9712 KB ok, correct split
23 Correct 71 ms 10096 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Correct 84 ms 8696 KB ok, correct split
26 Correct 28 ms 5120 KB ok, correct split
27 Correct 2 ms 2688 KB ok, correct split
28 Correct 101 ms 10616 KB ok, correct split
29 Correct 96 ms 10488 KB ok, correct split
30 Correct 102 ms 10744 KB ok, correct split
31 Correct 102 ms 11384 KB ok, correct split
32 Correct 106 ms 10616 KB ok, correct split
33 Correct 25 ms 4608 KB ok, no valid answer
34 Correct 39 ms 5632 KB ok, no valid answer
35 Correct 75 ms 8820 KB ok, no valid answer
36 Correct 88 ms 8696 KB ok, no valid answer
37 Correct 62 ms 8944 KB ok, no valid answer
38 Incorrect 2 ms 2688 KB invalid split: #1=1, #2=2, #3=6
39 Halted 0 ms 0 KB -