oj.uz

Submission #245008

# Submission time Handle Problem Language Result Execution time Memory
245008 2020-07-05T10:56:17 Z crossing0ver Split the Attractions (IOI19_split) C++17
11 / 100
 649 ms 1048576 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;
	}
	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]);
	}
	if (a == 1) return case1();
	
	bool flag = 1;
	for (int i = 0; i < n; i++) 
		if (adj[i].size() != 2) flag = 0;
	if (flag) return case2();
	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:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (v.size() != n) {
      ~~~~~~~~~^~~~

Subtask #1
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 Incorrect 151 ms 19680 KB jury found a solution, contestant did not
8 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 6 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 95 ms 8952 KB ok, correct split
5 Correct 104 ms 10360 KB ok, correct split
6 Correct 76 ms 7800 KB ok, correct split
7 Correct 103 ms 10104 KB ok, correct split
8 Correct 166 ms 11768 KB ok, correct split
9 Correct 96 ms 9848 KB ok, correct split
10 Correct 80 ms 10736 KB ok, correct split
11 Correct 81 ms 10736 KB ok, correct split
12 Correct 84 ms 10668 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 649 ms 1048576 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 Incorrect 151 ms 19680 KB jury found a solution, contestant did not
8 Halted 0 ms 0 KB -