oj.uz

답안 #718786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718786 2023-04-04T19:48:12 Z mseebacher Split the Attractions (IOI19_split) C++17
22 / 100
 496 ms 1048576 KB 
#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
 
#define MAX_N (int) 1e5+5
vector<int> ad[MAX_N];
vector<int> res;
vector<bool> vis(MAX_N,0);
vector<pair<int,int>> cnt;
vector<int> sz(MAX_N,0);
vector<int> max_child(MAX_N,0);
int node = -1;
int parent = -1;

void dfs_size(int x,int e){
	sz[x] = 1;
	max_child[x] = 0;
	for(auto s: ad[x]){
		if(s == e) continue;
		dfs_size(s,x);
		sz[x] += sz[s];
		max_child[x] = max(max_child[x],sz[s]);
	}
}

void dfs1(int x, int e){
	if(sz[x] < cnt[0].first) return;
	if(sz[x] >= cnt[0].first && sz[0] - sz[x] >= cnt[1].first){
		node = x;
		parent = e;
		return;
	}
	if(sz[x] >= cnt[1].first && sz[0] - sz[x] >= cnt[0].first){
		parent = x;
		node = e;
		return; 
	}
	for(auto s: ad[x]){
		if(s == e) continue;
		dfs1(s,x);
	}
}

void dfs2(int x,int e,int side){
	if(cnt[side].first == 0) return; 
	res[x] = cnt[side].second;
	cnt[side].first--;
	for(auto s: ad[x]){
		if(vis[s] || s == e) continue;
		dfs2(s,x,side);
	}
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for(int i = 0;i<(int)p.size();i++){
		ad[p[i]].push_back(q[i]);
		ad[q[i]].push_back(p[i]);
	}
	res.assign(n,0);
	if(a >= n-1 || b >= n-1 || c>=n-1) return res;
	cnt.push_back({a,1});
	cnt.push_back({b,2});
	cnt.push_back({c,3});
	sort(cnt.begin(),cnt.end());
	res.assign(n,cnt[2].second);
	dfs_size(0,-1);
	dfs1(0,-1);
	if(node == -1) return vector<int>(n,0);
	vis[node] = vis[parent] = 1;
	dfs2(node,node,0);
	dfs2(parent,parent,1);
	return res;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB ok, correct split
2 Runtime error 496 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3452 KB ok, correct split
2 Runtime error 489 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB ok, correct split
2 Correct 59 ms 8972 KB ok, correct split
3 Correct 24 ms 6060 KB ok, correct split
4 Correct 2 ms 3464 KB ok, correct split
5 Correct 79 ms 12416 KB ok, correct split
6 Correct 68 ms 12328 KB ok, correct split
7 Correct 66 ms 12408 KB ok, correct split
8 Correct 69 ms 12808 KB ok, correct split
9 Correct 67 ms 12408 KB ok, correct split
10 Correct 18 ms 5624 KB ok, no valid answer
11 Correct 30 ms 6764 KB ok, no valid answer
12 Correct 63 ms 10356 KB ok, no valid answer
13 Correct 56 ms 10188 KB ok, no valid answer
14 Correct 44 ms 10472 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 495 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB ok, correct split
2 Runtime error 496 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -