oj.uz

Submission #893459

# Submission time Handle Problem Language Result Execution time Memory
893459 2023-12-27T05:12:06 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
40 / 100
 83 ms 48212 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]){
          	if (found)
              	return;
			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 (p1 - sz[i] >= A and mn[i] < hei[u]){
			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

# Verdict Execution time Memory 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 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 80 ms 46208 KB ok, correct split
8 Correct 49 ms 22100 KB ok, correct split
9 Correct 67 ms 27844 KB ok, correct split
10 Correct 79 ms 47956 KB ok, correct split
11 Correct 83 ms 48212 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB ok, correct split
2 Correct 1 ms 4184 KB ok, correct split
3 Correct 1 ms 4188 KB ok, correct split
4 Correct 52 ms 14288 KB ok, correct split
5 Correct 38 ms 9692 KB ok, correct split
6 Correct 77 ms 47956 KB ok, correct split
7 Correct 70 ms 36176 KB ok, correct split
8 Correct 61 ms 11988 KB ok, correct split
9 Correct 39 ms 10176 KB ok, correct split
10 Correct 32 ms 10192 KB ok, correct split
11 Correct 33 ms 10196 KB ok, correct split
12 Correct 31 ms 10140 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB ok, correct split
2 Correct 49 ms 9688 KB ok, correct split
3 Correct 15 ms 6748 KB ok, correct split
4 Correct 2 ms 4188 KB ok, correct split
5 Correct 62 ms 22052 KB ok, correct split
6 Correct 51 ms 20820 KB ok, correct split
7 Correct 62 ms 19860 KB ok, correct split
8 Correct 63 ms 26716 KB ok, correct split
9 Correct 59 ms 19028 KB ok, correct split
10 Correct 15 ms 6232 KB ok, no valid answer
11 Correct 22 ms 7000 KB ok, no valid answer
12 Correct 50 ms 11992 KB ok, no valid answer
13 Correct 54 ms 10068 KB ok, no valid answer
14 Correct 56 ms 14028 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 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 2 ms 4256 KB invalid split: #1=2, #2=3, #3=6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory 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 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 80 ms 46208 KB ok, correct split
8 Correct 49 ms 22100 KB ok, correct split
9 Correct 67 ms 27844 KB ok, correct split
10 Correct 79 ms 47956 KB ok, correct split
11 Correct 83 ms 48212 KB ok, correct split
12 Correct 1 ms 4184 KB ok, correct split
13 Correct 1 ms 4184 KB ok, correct split
14 Correct 1 ms 4188 KB ok, correct split
15 Correct 52 ms 14288 KB ok, correct split
16 Correct 38 ms 9692 KB ok, correct split
17 Correct 77 ms 47956 KB ok, correct split
18 Correct 70 ms 36176 KB ok, correct split
19 Correct 61 ms 11988 KB ok, correct split
20 Correct 39 ms 10176 KB ok, correct split
21 Correct 32 ms 10192 KB ok, correct split
22 Correct 33 ms 10196 KB ok, correct split
23 Correct 31 ms 10140 KB ok, correct split
24 Correct 1 ms 4188 KB ok, correct split
25 Correct 49 ms 9688 KB ok, correct split
26 Correct 15 ms 6748 KB ok, correct split
27 Correct 2 ms 4188 KB ok, correct split
28 Correct 62 ms 22052 KB ok, correct split
29 Correct 51 ms 20820 KB ok, correct split
30 Correct 62 ms 19860 KB ok, correct split
31 Correct 63 ms 26716 KB ok, correct split
32 Correct 59 ms 19028 KB ok, correct split
33 Correct 15 ms 6232 KB ok, no valid answer
34 Correct 22 ms 7000 KB ok, no valid answer
35 Correct 50 ms 11992 KB ok, no valid answer
36 Correct 54 ms 10068 KB ok, no valid answer
37 Correct 56 ms 14028 KB ok, no valid answer
38 Correct 2 ms 4184 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 2 ms 4256 KB invalid split: #1=2, #2=3, #3=6
42 Halted 0 ms 0 KB -