oj.uz

Submission #960535

# Submission time Handle Problem Language Result Execution time Memory
960535 2024-04-10T15:28:57 Z vjudge1 Split the Attractions (IOI19_split) C++17
18 / 100
 76 ms 22672 KB 
#include "split.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

#define pb push_back

const int N = 1e5 + 10;

vector<int> g1[N];
vector<int> g2[N];
int res[N];

bool vis[N];
int n;
pair<int,int> f[3];

int v = -1;
int dfs(int x){
	vis[x] = 1;
	int sz = 1;
	for(auto u : g1[x]){
		if(!vis[u]){
			sz += dfs(u);
			g2[x].pb(u);
		}
	}
	if(v != -1)return sz;
	if(sz >= f[0].first && n - sz >= f[1].first){
		v = x;
	}

	return sz;
}



void dfsa(int x){
	if(!f[0].first)return;
	res[x] = f[0].second;
	f[0].first--;


	for(auto u : g2[x]){
		if(!res[u]){
			dfsa(u);

		}
	}
}

void dfsb(int x){
	if(!f[1].first)return;
	res[x] = f[1].second;
	f[1].first--;


	for(auto u : g2[x]){
		if(!res[u]){
			dfsb(u);
			
		}
	}
}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
	n = nn;
	f[0] = {a, 1};
	f[1] = {b, 2};
	f[2] = {c, 3};
	sort(f, f + 3);
	for(int i = 0;i<p.size();i++){
		g1[p[i]].pb(q[i]);
		g1[q[i]].pb(p[i]);

	}

	vector<int> ans(n , 0);

	dfs(0);
	if(v == -1)return ans;

	dfsa(v);
	dfsb(0);

	for(int i = 0;i<n;i++){
		if(!res[i])res[i]  =f[2].second;
		ans[i] = res[i];
	}



	return ans;

}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB ok, correct split
2 Correct 1 ms 5212 KB ok, correct split
3 Correct 1 ms 5212 KB ok, correct split
4 Correct 2 ms 5212 KB ok, correct split
5 Correct 1 ms 5468 KB ok, correct split
6 Correct 2 ms 5212 KB ok, correct split
7 Correct 52 ms 22360 KB ok, correct split
8 Correct 52 ms 20052 KB ok, correct split
9 Correct 52 ms 19284 KB ok, correct split
10 Correct 54 ms 22608 KB ok, correct split
11 Correct 53 ms 22672 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB ok, correct split
2 Correct 1 ms 5212 KB ok, correct split
3 Correct 2 ms 5212 KB ok, correct split
4 Correct 61 ms 19028 KB ok, correct split
5 Correct 55 ms 13556 KB ok, correct split
6 Correct 55 ms 22612 KB ok, correct split
7 Correct 52 ms 19812 KB ok, correct split
8 Correct 76 ms 17032 KB ok, correct split
9 Correct 45 ms 15056 KB ok, correct split
10 Correct 33 ms 12500 KB ok, correct split
11 Correct 32 ms 12384 KB ok, correct split
12 Correct 31 ms 12748 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB ok, correct split
2 Incorrect 49 ms 13312 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB ok, correct split
2 Correct 2 ms 5208 KB ok, no valid answer
3 Correct 1 ms 5212 KB ok, correct split
4 Correct 1 ms 5212 KB ok, correct split
5 Correct 2 ms 5464 KB ok, correct split
6 Correct 1 ms 5212 KB ok, correct split
7 Correct 1 ms 5212 KB ok, correct split
8 Correct 2 ms 5452 KB ok, correct split
9 Correct 4 ms 5716 KB ok, correct split
10 Correct 3 ms 5724 KB ok, correct split
11 Correct 2 ms 5468 KB ok, correct split
12 Correct 3 ms 5528 KB ok, correct split
13 Correct 1 ms 5212 KB ok, correct split
14 Correct 1 ms 5448 KB ok, correct split
15 Correct 1 ms 5208 KB ok, correct split
16 Correct 1 ms 5212 KB ok, correct split
17 Correct 2 ms 5456 KB ok, correct split
18 Correct 2 ms 5212 KB ok, correct split
19 Correct 2 ms 5468 KB ok, correct split
20 Correct 2 ms 5468 KB ok, correct split
21 Correct 3 ms 5976 KB ok, correct split
22 Incorrect 2 ms 5492 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB ok, correct split
2 Correct 1 ms 5212 KB ok, correct split
3 Correct 1 ms 5212 KB ok, correct split
4 Correct 2 ms 5212 KB ok, correct split
5 Correct 1 ms 5468 KB ok, correct split
6 Correct 2 ms 5212 KB ok, correct split
7 Correct 52 ms 22360 KB ok, correct split
8 Correct 52 ms 20052 KB ok, correct split
9 Correct 52 ms 19284 KB ok, correct split
10 Correct 54 ms 22608 KB ok, correct split
11 Correct 53 ms 22672 KB ok, correct split
12 Correct 2 ms 5212 KB ok, correct split
13 Correct 1 ms 5212 KB ok, correct split
14 Correct 2 ms 5212 KB ok, correct split
15 Correct 61 ms 19028 KB ok, correct split
16 Correct 55 ms 13556 KB ok, correct split
17 Correct 55 ms 22612 KB ok, correct split
18 Correct 52 ms 19812 KB ok, correct split
19 Correct 76 ms 17032 KB ok, correct split
20 Correct 45 ms 15056 KB ok, correct split
21 Correct 33 ms 12500 KB ok, correct split
22 Correct 32 ms 12384 KB ok, correct split
23 Correct 31 ms 12748 KB ok, correct split
24 Correct 2 ms 5212 KB ok, correct split
25 Incorrect 49 ms 13312 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -