oj.uz

Submission #245176

# Submission time Handle Problem Language Result Execution time Memory
245176 2020-07-05T16:28:03 Z crossing0ver Split the Attractions (IOI19_split) C++17
18 / 100
 2000 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;
}
int P[MXN],seen[MXN];
vi e[MXN];
void SDS(int v) {
	seen[v] = 1;
	for (int i : adj[v]) {
		if (seen[i]) continue;
		e[v].pb(i);
		e[i].pb(v);
		SDS(i);
	}
}
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]);
	}
	int 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();
	for (int i = 0;i  < n; i++) {
	dfs(i,-1,0);
	if (flag) break;
	}
	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 8 ms 4992 KB ok, correct split
2 Correct 8 ms 5120 KB ok, correct split
3 Correct 8 ms 4992 KB ok, correct split
4 Correct 8 ms 4992 KB ok, correct split
5 Correct 8 ms 4992 KB ok, correct split
6 Correct 7 ms 4992 KB ok, correct split
7 Correct 123 ms 22008 KB ok, correct split
8 Correct 145 ms 14816 KB ok, correct split
9 Correct 118 ms 22136 KB ok, correct split
10 Correct 77 ms 10996 KB ok, correct split
11 Correct 81 ms 11124 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 7 ms 5044 KB ok, correct split
4 Correct 88 ms 11256 KB ok, correct split
5 Correct 110 ms 12712 KB ok, correct split
6 Correct 81 ms 10996 KB ok, correct split
7 Correct 104 ms 12412 KB ok, correct split
8 Correct 131 ms 14200 KB ok, correct split
9 Correct 97 ms 12152 KB ok, correct split
10 Correct 82 ms 13040 KB ok, correct split
11 Correct 84 ms 13040 KB ok, correct split
12 Correct 90 ms 13040 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 114 ms 13816 KB ok, correct split
3 Correct 36 ms 7424 KB ok, correct split
4 Correct 8 ms 4992 KB ok, correct split
5 Correct 144 ms 15992 KB ok, correct split
6 Correct 134 ms 15864 KB ok, correct split
7 Correct 137 ms 16504 KB ok, correct split
8 Correct 123 ms 16760 KB ok, correct split
9 Correct 131 ms 16376 KB ok, correct split
10 Execution timed out 2069 ms 6784 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 709 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 8 ms 4992 KB ok, correct split
2 Correct 8 ms 5120 KB ok, correct split
3 Correct 8 ms 4992 KB ok, correct split
4 Correct 8 ms 4992 KB ok, correct split
5 Correct 8 ms 4992 KB ok, correct split
6 Correct 7 ms 4992 KB ok, correct split
7 Correct 123 ms 22008 KB ok, correct split
8 Correct 145 ms 14816 KB ok, correct split
9 Correct 118 ms 22136 KB ok, correct split
10 Correct 77 ms 10996 KB ok, correct split
11 Correct 81 ms 11124 KB ok, correct split
12 Correct 8 ms 4992 KB ok, correct split
13 Correct 7 ms 4992 KB ok, correct split
14 Correct 7 ms 5044 KB ok, correct split
15 Correct 88 ms 11256 KB ok, correct split
16 Correct 110 ms 12712 KB ok, correct split
17 Correct 81 ms 10996 KB ok, correct split
18 Correct 104 ms 12412 KB ok, correct split
19 Correct 131 ms 14200 KB ok, correct split
20 Correct 97 ms 12152 KB ok, correct split
21 Correct 82 ms 13040 KB ok, correct split
22 Correct 84 ms 13040 KB ok, correct split
23 Correct 90 ms 13040 KB ok, correct split
24 Correct 7 ms 4992 KB ok, correct split
25 Correct 114 ms 13816 KB ok, correct split
26 Correct 36 ms 7424 KB ok, correct split
27 Correct 8 ms 4992 KB ok, correct split
28 Correct 144 ms 15992 KB ok, correct split
29 Correct 134 ms 15864 KB ok, correct split
30 Correct 137 ms 16504 KB ok, correct split
31 Correct 123 ms 16760 KB ok, correct split
32 Correct 131 ms 16376 KB ok, correct split
33 Execution timed out 2069 ms 6784 KB Time limit exceeded
34 Halted 0 ms 0 KB -