oj.uz

Submission #244985

# Submission time Handle Problem Language Result Execution time Memory
244985 2020-07-05T10:40:36 Z crossing0ver Split the Attractions (IOI19_split) C++17
11 / 100
 790 ms 1048580 KB 
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define local
#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;
	}
	dfs(v,p,1);
	flag = mn;
	if (p != -1)
	dfs(p,v,1);
}
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]);
	}
	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;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB ok, correct split
2 Correct 7 ms 2688 KB ok, correct split
3 Correct 7 ms 2688 KB ok, correct split
4 Runtime error 722 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 8 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 101 ms 8952 KB ok, correct split
5 Correct 110 ms 10284 KB ok, correct split
6 Correct 81 ms 7800 KB ok, correct split
7 Correct 117 ms 10104 KB ok, correct split
8 Correct 142 ms 11768 KB ok, correct split
9 Correct 101 ms 9848 KB ok, correct split
10 Correct 93 ms 10736 KB ok, correct split
11 Correct 89 ms 10736 KB ok, correct split
12 Correct 88 ms 10736 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Runtime error 790 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 728 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 7 ms 2688 KB ok, correct split
2 Correct 7 ms 2688 KB ok, correct split
3 Correct 7 ms 2688 KB ok, correct split
4 Runtime error 722 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -