oj.uz

Submission #245183

# Submission time Handle Problem Language Result Execution time Memory
245183 2020-07-05T16:32:49 Z crossing0ver Split the Attractions (IOI19_split) C++17
11 / 100
 129 ms 15096 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,vis[MXN];
set<int> ans[4];
int P[MXN];
void dfs(int v,int p,int type) {
	vis[v] = 1;
	if (type == 1 && X[flag]) {
		X[flag]--;
		ans[flag].insert(v);
	}
	sz[v] = 1;
	for (int i : adj[v]) {
		if (vis[i]) 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]);
	}
	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();
	int lim =  n <= 2500 && m <= 5000 ? n : 1;
	for (int i = 0;i  < lim; i++) {
		memset(vis,0,sizeof vis);
	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:92: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 7 ms 2688 KB ok, correct split
5 Correct 6 ms 2816 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Incorrect 102 ms 15096 KB invalid split: #1=1, #2=1, #3=99998
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 91 ms 9080 KB ok, correct split
5 Correct 99 ms 10488 KB ok, correct split
6 Correct 79 ms 8820 KB ok, correct split
7 Correct 101 ms 10488 KB ok, correct split
8 Correct 129 ms 12028 KB ok, correct split
9 Correct 100 ms 10104 KB ok, correct split
10 Correct 79 ms 10864 KB ok, correct split
11 Correct 82 ms 10992 KB ok, correct split
12 Correct 86 ms 10992 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB ok, correct split
2 Incorrect 82 ms 9720 KB invalid split: #1=9155, #2=1, #3=90844
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3072 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 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 7 ms 2688 KB ok, correct split
5 Correct 6 ms 2816 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Incorrect 102 ms 15096 KB invalid split: #1=1, #2=1, #3=99998
8 Halted 0 ms 0 KB -