oj.uz

Submission #245026

# Submission time Handle Problem Language Result Execution time Memory
245026 2020-07-05T11:09:07 Z crossing0ver Split the Attractions (IOI19_split) C++17
40 / 100
 644 ms 1048580 KB 
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#ifndef local
#include "split.h"
#endif
using namespace std;
const int MXN = 1e5 +5; 
int n,a,b,c,m;
vector<int> adj[MXN];
vi case1() {
	vector<bool> vis(n);
	vis[0] = 1;
	queue<int> q;
	set<int> sec;
	int cnt = b;
	q.push(0);
	while(!q.empty() && cnt) {
		cnt--;
		int v = q.front();
		sec.insert(v);
		q.pop();
		for (int i :adj[v]) {
			if (!vis[i]) {
				vis[i] = 1;
				q.push(i);
			}
		}
	}
	vector<int> ans(n);
	for (int i : sec) ans[i] = 2;
	for (int i = 0,flag = 0; i < n; i++) {
		if (sec.count(i)) continue;
		if (flag == 0) flag = 1, ans[i] = 1;
		else ans[i] = 3;
	} 
	return ans;
}

int sz[MXN],flag,X[4],mn;
set<int> ans[4];
void dfs(int v,int p,int type) {
	if (type == 1 && X[flag]) {
		X[flag]--;
		ans[flag].insert(v);
	}
	sz[v] = 1;
	for (int i : adj[v]) {
		if (i == p) continue;
		dfs(i,v,type);
		sz[v] += sz[i];
	}
	if (flag) return;
	if (sz[v] >= a && n - sz[v] >= min(b,c)) {
		flag = 1;
		if (n - sz[v] >= b) mn = 2;
		else mn = 3;
	}
	else if (sz[v] >= b && n - sz[v] >= min(a,c)) {
		flag = 2;
		if (n - sz[v] >= a) mn = 1;
		else mn = 3;
	}
	else if (sz[v] >= c && n - sz[v] >= min(a,b)) {
		flag = 3;
		if (n - sz[v] >= a) mn = 1;
		else mn = 2;
	}
	else return;
	dfs(v,p,1);
	flag = mn;
	if (p != -1)
	dfs(p,v,1);
}
vi case2() {
	int cnt = 0;
	vi v,vis(n);
	int cur = 0;
	while(cnt != n) {
		cnt++;
		vis[cur] = 1;
		v.push_back(cur);
		for (int i : adj[cur]) {
			if (vis[i]) continue;
			cur = i;
			break;
		}
	}
	vi ans(n);
	if (v.size() != n) {
		while(true){
			
		}
	}
	for (int i = 0; i < a;i++) ans[v[i]] = 1;
	for (int i = a; i < a + b; i++) ans[v[i]] = 2;
	for (int i = a+b; i < n; i++) ans[v[i]] = 3;
	return ans;
}
vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) {
	n = n1,a = a1,b=b1,c=c1;
	X[1] = a,X[2] = b, X[3] = c;
	m = p.size();
	for (int i = 0;i < m; i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	bool G= 1;
	for (int i = 0; i < n; i++) 
		if (adj[i].size() != 2) G = 0;
	if (G) return case2();
	if (a == 1) return case1();
	dfs(0,-1,0);
	vector<int> res(n),vis(n);
	if (flag == 0) return res;
	for (int j = 1; j <= 3; j++)
	for (int i : ans[j]) res[i] = j,vis[i] = 1;
	
	int id;
	for (int i = 1; i <= 3; i++) if (ans[i].empty()) id = i;
	for (int i = 0; i < n; i++) if (!vis[i]) res[i] = id;
	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> case2()':
split.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (v.size() != n) {
      ~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 156 ms 19712 KB ok, correct split
8 Correct 171 ms 13560 KB ok, correct split
9 Correct 145 ms 20984 KB ok, correct split
10 Correct 112 ms 9852 KB ok, correct split
11 Correct 113 ms 9788 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 7 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 96 ms 8952 KB ok, correct split
5 Correct 102 ms 10232 KB ok, correct split
6 Correct 96 ms 8820 KB ok, correct split
7 Correct 115 ms 10104 KB ok, correct split
8 Correct 131 ms 12024 KB ok, correct split
9 Correct 94 ms 9848 KB ok, correct split
10 Correct 80 ms 10736 KB ok, correct split
11 Correct 82 ms 10668 KB ok, correct split
12 Correct 100 ms 10736 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 107 ms 11512 KB ok, correct split
3 Correct 31 ms 5112 KB ok, correct split
4 Correct 7 ms 2688 KB ok, correct split
5 Correct 129 ms 13688 KB ok, correct split
6 Correct 128 ms 13432 KB ok, correct split
7 Correct 128 ms 14072 KB ok, correct split
8 Correct 127 ms 14456 KB ok, correct split
9 Correct 154 ms 13944 KB ok, correct split
10 Correct 28 ms 4608 KB ok, no valid answer
11 Correct 35 ms 5752 KB ok, no valid answer
12 Correct 72 ms 8820 KB ok, no valid answer
13 Correct 78 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 Runtime error 644 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 156 ms 19712 KB ok, correct split
8 Correct 171 ms 13560 KB ok, correct split
9 Correct 145 ms 20984 KB ok, correct split
10 Correct 112 ms 9852 KB ok, correct split
11 Correct 113 ms 9788 KB ok, correct split
12 Correct 6 ms 2688 KB ok, correct split
13 Correct 7 ms 2688 KB ok, correct split
14 Correct 6 ms 2688 KB ok, correct split
15 Correct 96 ms 8952 KB ok, correct split
16 Correct 102 ms 10232 KB ok, correct split
17 Correct 96 ms 8820 KB ok, correct split
18 Correct 115 ms 10104 KB ok, correct split
19 Correct 131 ms 12024 KB ok, correct split
20 Correct 94 ms 9848 KB ok, correct split
21 Correct 80 ms 10736 KB ok, correct split
22 Correct 82 ms 10668 KB ok, correct split
23 Correct 100 ms 10736 KB ok, correct split
24 Correct 6 ms 2688 KB ok, correct split
25 Correct 107 ms 11512 KB ok, correct split
26 Correct 31 ms 5112 KB ok, correct split
27 Correct 7 ms 2688 KB ok, correct split
28 Correct 129 ms 13688 KB ok, correct split
29 Correct 128 ms 13432 KB ok, correct split
30 Correct 128 ms 14072 KB ok, correct split
31 Correct 127 ms 14456 KB ok, correct split
32 Correct 154 ms 13944 KB ok, correct split
33 Correct 28 ms 4608 KB ok, no valid answer
34 Correct 35 ms 5752 KB ok, no valid answer
35 Correct 72 ms 8820 KB ok, no valid answer
36 Correct 78 ms 8696 KB ok, no valid answer
37 Correct 62 ms 8944 KB ok, no valid answer
38 Runtime error 644 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Halted 0 ms 0 KB -