oj.uz

답안 #893429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893429 2023-12-27T04:48:57 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
40 / 100
 136 ms 87244 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include "split.h"
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

vector<vector<int>> v;
vector<int> nei[N];
int A,B;
int mn[N];
int sz[N];
int hei[N];
bool seen[N];
int color[N];
bool found = false;
int K;

void dfs_color(int u,int c){
	if (seen[u])
		return;
	if (K<=0)
		return;
	color[u] = c;
	seen[u] = true;
	K--;
	for (int i : nei[u]){
		if (seen[i])
			continue;
		dfs_color(i,c);
	}
}

void dfs(int u,int h = 1){
	sz[u] = 1;
	hei[u] = h++;
	seen[u] = true;
	mn[u] = hei[u];
	for (int i : nei[u]){
		if (seen[i]){
			mn[u] = min(mn[u],hei[i]);
			continue;
		}
		dfs(i,h);
		sz[u] += sz[i];
		if (mn[i])
			mn[u] = min(mn[u],mn[i]);
	}
}

// #################################### reset seen
bool called = false;
void call(int u,set<int> s,int c,int Sz){
	if (called)
		return;
	called = true;
	memset(seen,false,sizeof seen);
	seen[u] = true;
	color[u] = c;
	Sz--;
	K = Sz;
	for (int i : s)
		dfs_color(i,c);
}

void dfs2(int u){
	seen[u] = true; 
	int p1 = sz[u];
	int p2 = sz[1] - sz[u];

	set<int> s;

	for (int  i : nei[u])
		if (!seen[i]){
			s.insert(i);
			dfs2(i);
		}

	if (p1>=A and p2>=B){
		call(u,s,v[0][1],A);
		K = B;
		dfs_color(1,v[1][1]);
		found = true;
		return;
	}
	else if (p1>=B and p2>=A){
		call(u,s,v[1][1],B);
		K = A;
		dfs_color(1,v[0][1]);
		found = true;
		return;
	}

	for (int i : nei[u]){
		if (seen[i])
			continue;

		if (found)
			return;
		
		if (mn[i]>=hei[u])
			continue;
		
		if (p1 - sz[i] >= A){
			s.erase(i);
			p1 -= sz[i];
			p2 += sz[i];
		}
		if (p1>=A and p2>=B){
			call(u,s,v[0][1],A);
			K = B;
			dfs_color(1,v[1][1]);
			found = true;
			return;
		}
		else if (p1>=B and p2>=A){
			call(u,s,v[1][1],B);
			K = A;
			dfs_color(1,v[0][1]);
			found = true;
			return;
		}
	}
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	int m = p.size();

	for (int i=0;i<m;i++){
		p[i]++;
		q[i]++;
		nei[p[i]].push_back(q[i]);
		nei[q[i]].push_back(p[i]);
	}
	v.push_back({a,1});
	v.push_back({b,2});
	v.push_back({c,3});

	sort(begin(v),end(v));

	A = v[0][0];
	B = v[1][0];

	dfs(1,1);

	memset(seen,false,sizeof seen);

	dfs2(1);

	vector<int> col;
	if (!found){
		for (int i=1;i<=n;i++)
			col.push_back(0);
		return col;
	}
	for (int i=1;i<=n;i++){
		if (color[i]==0)
			col.push_back(v[2][1]);
		else
			col.push_back(color[i]);
	}
	return col;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 1 ms 4240 KB ok, correct split
3 Correct 1 ms 4184 KB ok, correct split
4 Correct 1 ms 4188 KB ok, correct split
5 Correct 1 ms 4188 KB ok, correct split
6 Correct 1 ms 4188 KB ok, correct split
7 Correct 93 ms 46172 KB ok, correct split
8 Correct 89 ms 35152 KB ok, correct split
9 Correct 67 ms 27668 KB ok, correct split
10 Correct 128 ms 87008 KB ok, correct split
11 Correct 99 ms 48212 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 1 ms 4188 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 92 ms 28420 KB ok, correct split
5 Correct 38 ms 9684 KB ok, correct split
6 Correct 136 ms 87244 KB ok, correct split
7 Correct 83 ms 39248 KB ok, correct split
8 Correct 77 ms 12052 KB ok, correct split
9 Correct 41 ms 9968 KB ok, correct split
10 Correct 42 ms 11840 KB ok, correct split
11 Correct 47 ms 14008 KB ok, correct split
12 Correct 48 ms 14216 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB ok, correct split
2 Correct 46 ms 9688 KB ok, correct split
3 Correct 18 ms 6744 KB ok, correct split
4 Correct 1 ms 4188 KB ok, correct split
5 Correct 68 ms 22100 KB ok, correct split
6 Correct 79 ms 21012 KB ok, correct split
7 Correct 58 ms 19916 KB ok, correct split
8 Correct 76 ms 26572 KB ok, correct split
9 Correct 64 ms 19028 KB ok, correct split
10 Correct 15 ms 6232 KB ok, no valid answer
11 Correct 26 ms 7768 KB ok, no valid answer
12 Correct 57 ms 13092 KB ok, no valid answer
13 Correct 45 ms 11088 KB ok, no valid answer
14 Correct 57 ms 15052 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 1 ms 4188 KB ok, no valid answer
3 Correct 1 ms 4188 KB ok, correct split
4 Incorrect 1 ms 4184 KB invalid split: #1=2, #2=3, #3=6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 1 ms 4240 KB ok, correct split
3 Correct 1 ms 4184 KB ok, correct split
4 Correct 1 ms 4188 KB ok, correct split
5 Correct 1 ms 4188 KB ok, correct split
6 Correct 1 ms 4188 KB ok, correct split
7 Correct 93 ms 46172 KB ok, correct split
8 Correct 89 ms 35152 KB ok, correct split
9 Correct 67 ms 27668 KB ok, correct split
10 Correct 128 ms 87008 KB ok, correct split
11 Correct 99 ms 48212 KB ok, correct split
12 Correct 1 ms 4188 KB ok, correct split
13 Correct 1 ms 4188 KB ok, correct split
14 Correct 1 ms 4188 KB ok, correct split
15 Correct 92 ms 28420 KB ok, correct split
16 Correct 38 ms 9684 KB ok, correct split
17 Correct 136 ms 87244 KB ok, correct split
18 Correct 83 ms 39248 KB ok, correct split
19 Correct 77 ms 12052 KB ok, correct split
20 Correct 41 ms 9968 KB ok, correct split
21 Correct 42 ms 11840 KB ok, correct split
22 Correct 47 ms 14008 KB ok, correct split
23 Correct 48 ms 14216 KB ok, correct split
24 Correct 1 ms 4184 KB ok, correct split
25 Correct 46 ms 9688 KB ok, correct split
26 Correct 18 ms 6744 KB ok, correct split
27 Correct 1 ms 4188 KB ok, correct split
28 Correct 68 ms 22100 KB ok, correct split
29 Correct 79 ms 21012 KB ok, correct split
30 Correct 58 ms 19916 KB ok, correct split
31 Correct 76 ms 26572 KB ok, correct split
32 Correct 64 ms 19028 KB ok, correct split
33 Correct 15 ms 6232 KB ok, no valid answer
34 Correct 26 ms 7768 KB ok, no valid answer
35 Correct 57 ms 13092 KB ok, no valid answer
36 Correct 45 ms 11088 KB ok, no valid answer
37 Correct 57 ms 15052 KB ok, no valid answer
38 Correct 1 ms 4188 KB ok, correct split
39 Correct 1 ms 4188 KB ok, no valid answer
40 Correct 1 ms 4188 KB ok, correct split
41 Incorrect 1 ms 4184 KB invalid split: #1=2, #2=3, #3=6
42 Halted 0 ms 0 KB -