oj.uz

Submission #891467

# Submission time Handle Problem Language Result Execution time Memory
891467 2023-12-23T05:10:57 Z Jawad_Akbar_JJ Split the Attractions (IOI19_split) C++17
40 / 100
 2000 ms 22224 KB 
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <vector>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include "split.h"

using namespace std;

const int N = 100005 + 1;
vector<int> nei[N],ch[N];
int color[N],A,B;
vector<vector<int>> v;
int sz[N],blocked = -1;
bool seen[N],found = false;
int root;
bool Seen[N];


void color_it(int u,int c){
	color[u] = c;
	A--;
	if (A == 0)
		return;
	for (int i : ch[u]){
		if (blocked == i)
			continue;
		color_it(i,c);
		if (A==0)
			return;
	}
}



void dfs(int u){
	seen[u] = true;
	sz[u] = 1;
	for (int i : nei[u]){
		if (seen[i])
			continue;
		ch[u].push_back(i);
		dfs(i);
		sz[u] += sz[i];
	}
}

void dfs2(int u){
	for (int i : ch[u]){
		if (found)
			return;
		if (sz[i]>=A and (sz[root] - sz[i]) >= B){
			color_it(i,v[0][1]);
			A = B;
			blocked = i;
			color_it(root,v[1][1]);
			found = true;
			return;
		}
		dfs2(i);
	}
}


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

	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 = {{a,1},{b,2},{c,3}};
	sort(begin(v),end(v));
	A = v[0][0];
	B = v[1][0];
	for (int i=1;i<=80;i++){

		root = rand()%(n+1);
		if (Seen[root]){
			i--;
			continue;
		}
		Seen[root] = true;


		for (int i=1;i<=n;i++)
			ch[i].clear(),seen[i] = false;
		blocked = -1;
		

		dfs(root);
		dfs2(root);
		if (!found)
			continue;
		vector<int> ans;

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

	vector<int> ans;

	for (int i=1;i<=n;i++)
		ans.push_back(0);
	
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 55 ms 21264 KB ok, correct split
8 Correct 52 ms 18764 KB ok, correct split
9 Correct 55 ms 20172 KB ok, correct split
10 Correct 49 ms 22220 KB ok, correct split
11 Correct 71 ms 22220 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 58 ms 18128 KB ok, correct split
5 Correct 44 ms 13008 KB ok, correct split
6 Correct 51 ms 22224 KB ok, correct split
7 Correct 54 ms 18380 KB ok, correct split
8 Correct 70 ms 15516 KB ok, correct split
9 Correct 42 ms 14480 KB ok, correct split
10 Correct 31 ms 12120 KB ok, correct split
11 Correct 32 ms 12116 KB ok, correct split
12 Correct 34 ms 12120 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 43 ms 13212 KB ok, correct split
3 Correct 17 ms 8792 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 48 ms 17692 KB ok, correct split
6 Correct 56 ms 18040 KB ok, correct split
7 Correct 54 ms 17868 KB ok, correct split
8 Correct 50 ms 17356 KB ok, correct split
9 Correct 47 ms 17612 KB ok, correct split
10 Correct 143 ms 8272 KB ok, no valid answer
11 Correct 227 ms 9736 KB ok, no valid answer
12 Correct 301 ms 12732 KB ok, no valid answer
13 Correct 470 ms 13292 KB ok, no valid answer
14 Correct 143 ms 12184 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Execution timed out 2054 ms 5720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 55 ms 21264 KB ok, correct split
8 Correct 52 ms 18764 KB ok, correct split
9 Correct 55 ms 20172 KB ok, correct split
10 Correct 49 ms 22220 KB ok, correct split
11 Correct 71 ms 22220 KB ok, correct split
12 Correct 2 ms 5724 KB ok, correct split
13 Correct 2 ms 5724 KB ok, correct split
14 Correct 2 ms 5724 KB ok, correct split
15 Correct 58 ms 18128 KB ok, correct split
16 Correct 44 ms 13008 KB ok, correct split
17 Correct 51 ms 22224 KB ok, correct split
18 Correct 54 ms 18380 KB ok, correct split
19 Correct 70 ms 15516 KB ok, correct split
20 Correct 42 ms 14480 KB ok, correct split
21 Correct 31 ms 12120 KB ok, correct split
22 Correct 32 ms 12116 KB ok, correct split
23 Correct 34 ms 12120 KB ok, correct split
24 Correct 2 ms 5720 KB ok, correct split
25 Correct 43 ms 13212 KB ok, correct split
26 Correct 17 ms 8792 KB ok, correct split
27 Correct 2 ms 5720 KB ok, correct split
28 Correct 48 ms 17692 KB ok, correct split
29 Correct 56 ms 18040 KB ok, correct split
30 Correct 54 ms 17868 KB ok, correct split
31 Correct 50 ms 17356 KB ok, correct split
32 Correct 47 ms 17612 KB ok, correct split
33 Correct 143 ms 8272 KB ok, no valid answer
34 Correct 227 ms 9736 KB ok, no valid answer
35 Correct 301 ms 12732 KB ok, no valid answer
36 Correct 470 ms 13292 KB ok, no valid answer
37 Correct 143 ms 12184 KB ok, no valid answer
38 Correct 2 ms 5724 KB ok, correct split
39 Execution timed out 2054 ms 5720 KB Time limit exceeded
40 Halted 0 ms 0 KB -