oj.uz

답안 #244985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -