oj.uz

Submission #893481

# Submission time Handle Problem Language Result Execution time Memory
893481 2023-12-27T05:42:51 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
40 / 100
 87 ms 53656 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <cassert>
#include "split.h"
#include <algorithm>
 
using namespace std;
const int N = 1e5 + 10;
 
vector<vector<int>> v;
vector<int> nei[N],ch[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;
		}
		ch[u].push_back(i);
		dfs(i,h);
		sz[u] += sz[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){
	int p1 = sz[u];
	int p2 = sz[1] - sz[u];
 
	set<int> s;
 
	for (int  i : ch[u]){
		s.insert(i);
		dfs2(i);
		if (found)
          	return;
	}
 
	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 : ch[u]){
		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;
		}
		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 6488 KB ok, correct split
2 Correct 1 ms 6492 KB ok, correct split
3 Correct 1 ms 6744 KB ok, correct split
4 Correct 1 ms 6744 KB ok, correct split
5 Correct 1 ms 6492 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 85 ms 51832 KB ok, correct split
8 Correct 68 ms 27732 KB ok, correct split
9 Correct 69 ms 33248 KB ok, correct split
10 Correct 82 ms 53584 KB ok, correct split
11 Correct 87 ms 53656 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok, correct split
2 Correct 1 ms 6492 KB ok, correct split
3 Correct 1 ms 6492 KB ok, correct split
4 Correct 61 ms 19456 KB ok, correct split
5 Correct 42 ms 13788 KB ok, correct split
6 Correct 78 ms 53332 KB ok, correct split
7 Correct 75 ms 41832 KB ok, correct split
8 Correct 64 ms 16336 KB ok, correct split
9 Correct 47 ms 15576 KB ok, correct split
10 Correct 35 ms 12792 KB ok, correct split
11 Correct 37 ms 12880 KB ok, correct split
12 Correct 33 ms 13032 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB ok, correct split
2 Correct 56 ms 13784 KB ok, correct split
3 Correct 16 ms 9660 KB ok, correct split
4 Correct 1 ms 6492 KB ok, correct split
5 Correct 68 ms 27644 KB ok, correct split
6 Correct 69 ms 26452 KB ok, correct split
7 Correct 65 ms 25348 KB ok, correct split
8 Correct 73 ms 32336 KB ok, correct split
9 Correct 65 ms 24656 KB ok, correct split
10 Correct 16 ms 9048 KB ok, no valid answer
11 Correct 23 ms 10220 KB ok, no valid answer
12 Correct 51 ms 15104 KB ok, no valid answer
13 Correct 50 ms 13916 KB ok, no valid answer
14 Correct 57 ms 16720 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB ok, correct split
2 Correct 1 ms 6492 KB ok, no valid answer
3 Correct 1 ms 6492 KB ok, correct split
4 Incorrect 1 ms 6492 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 6488 KB ok, correct split
2 Correct 1 ms 6492 KB ok, correct split
3 Correct 1 ms 6744 KB ok, correct split
4 Correct 1 ms 6744 KB ok, correct split
5 Correct 1 ms 6492 KB ok, correct split
6 Correct 1 ms 6492 KB ok, correct split
7 Correct 85 ms 51832 KB ok, correct split
8 Correct 68 ms 27732 KB ok, correct split
9 Correct 69 ms 33248 KB ok, correct split
10 Correct 82 ms 53584 KB ok, correct split
11 Correct 87 ms 53656 KB ok, correct split
12 Correct 1 ms 6492 KB ok, correct split
13 Correct 1 ms 6492 KB ok, correct split
14 Correct 1 ms 6492 KB ok, correct split
15 Correct 61 ms 19456 KB ok, correct split
16 Correct 42 ms 13788 KB ok, correct split
17 Correct 78 ms 53332 KB ok, correct split
18 Correct 75 ms 41832 KB ok, correct split
19 Correct 64 ms 16336 KB ok, correct split
20 Correct 47 ms 15576 KB ok, correct split
21 Correct 35 ms 12792 KB ok, correct split
22 Correct 37 ms 12880 KB ok, correct split
23 Correct 33 ms 13032 KB ok, correct split
24 Correct 2 ms 6492 KB ok, correct split
25 Correct 56 ms 13784 KB ok, correct split
26 Correct 16 ms 9660 KB ok, correct split
27 Correct 1 ms 6492 KB ok, correct split
28 Correct 68 ms 27644 KB ok, correct split
29 Correct 69 ms 26452 KB ok, correct split
30 Correct 65 ms 25348 KB ok, correct split
31 Correct 73 ms 32336 KB ok, correct split
32 Correct 65 ms 24656 KB ok, correct split
33 Correct 16 ms 9048 KB ok, no valid answer
34 Correct 23 ms 10220 KB ok, no valid answer
35 Correct 51 ms 15104 KB ok, no valid answer
36 Correct 50 ms 13916 KB ok, no valid answer
37 Correct 57 ms 16720 KB ok, no valid answer
38 Correct 2 ms 6492 KB ok, correct split
39 Correct 1 ms 6492 KB ok, no valid answer
40 Correct 1 ms 6492 KB ok, correct split
41 Incorrect 1 ms 6492 KB invalid split: #1=2, #2=3, #3=6
42 Halted 0 ms 0 KB -