oj.uz

답안 #244998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244998 2020-07-05T10:48:27 Z crossing0ver Split the Attractions (IOI19_split) C++17
11 / 100
 641 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);
	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;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 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 148 ms 20856 KB jury found a solution, contestant did not
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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 100 ms 8952 KB ok, correct split
5 Correct 101 ms 10232 KB ok, correct split
6 Correct 82 ms 7800 KB ok, correct split
7 Correct 107 ms 10108 KB ok, correct split
8 Correct 138 ms 11896 KB ok, correct split
9 Correct 103 ms 9848 KB ok, correct split
10 Correct 88 ms 10860 KB ok, correct split
11 Correct 82 ms 10736 KB ok, correct split
12 Correct 88 ms 10736 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2816 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 641 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

# 결과 실행 시간 메모리 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 148 ms 20856 KB jury found a solution, contestant did not
8 Halted 0 ms 0 KB -