oj.uz

Submission #293783

# Submission time Handle Problem Language Result Execution time Memory
293783 2020-09-08T12:04:06 Z egekabas Split the Attractions (IOI19_split) C++14
22 / 100
 110 ms 11448 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);
	if(a == 1 || 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));
	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:88:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |  if(a == 1 || p.size() != n-1){
      |               ~~~~~~~~~^~~~~~
split.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  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 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Incorrect 2 ms 2688 KB invalid split: #1=1, #2=1, #3=2
5 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 Correct 2 ms 2688 KB ok, correct split
3 Incorrect 2 ms 2688 KB invalid split: #1=1, #2=1, #3=3
4 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 86 ms 8696 KB ok, correct split
3 Correct 30 ms 5116 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 104 ms 10616 KB ok, correct split
6 Correct 110 ms 10364 KB ok, correct split
7 Correct 105 ms 10744 KB ok, correct split
8 Correct 107 ms 11448 KB ok, correct split
9 Correct 108 ms 10616 KB ok, correct split
10 Correct 25 ms 4600 KB ok, no valid answer
11 Correct 37 ms 5624 KB ok, no valid answer
12 Correct 82 ms 8820 KB ok, no valid answer
13 Correct 90 ms 8696 KB ok, no valid answer
14 Correct 63 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=1, #3=7
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 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Incorrect 2 ms 2688 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -