oj.uz

Submission #293780

# Submission time Handle Problem Language Result Execution time Memory
293780 2020-09-08T12:00:38 Z egekabas Split the Attractions (IOI19_split) C++14
22 / 100
 631 ms 1048580 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;
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	ans.resize(n);
	col = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(col));
	for(int i = 0; i < p.size(); ++i){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	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:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0; i < p.size(); ++i){
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Runtime error 631 ms 1048580 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 2 ms 2688 KB ok, correct split
2 Runtime error 603 ms 1048580 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 2 ms 2688 KB ok, correct split
2 Correct 91 ms 9848 KB ok, correct split
3 Correct 30 ms 5500 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 109 ms 11768 KB ok, correct split
6 Correct 114 ms 11512 KB ok, correct split
7 Correct 104 ms 11896 KB ok, correct split
8 Correct 109 ms 12536 KB ok, correct split
9 Correct 121 ms 11704 KB ok, correct split
10 Correct 25 ms 4984 KB ok, no valid answer
11 Correct 40 ms 6224 KB ok, no valid answer
12 Correct 75 ms 9972 KB ok, no valid answer
13 Correct 93 ms 9848 KB ok, no valid answer
14 Correct 67 ms 10036 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 614 ms 1048580 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 2 ms 2688 KB ok, correct split
2 Runtime error 631 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -