oj.uz

Submission #955696

# Submission time Handle Problem Language Result Execution time Memory
955696 2024-03-31T10:34:55 Z Macker Split the Attractions (IOI19_split) C++17
40 / 100
 67 ms 22728 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

vector<vector<int>> adj;
vector<vector<int>> chld;
vector<bool> vis;
vector<int> res;
vector<pii> f;
vector<int> coln;
int v = -1;
bool r = 0;
int n;

int dfs(int a){
	vis[a] = 1;
	int ret = 1;
	for (auto b : adj[a]) {
		if(!vis[b]){
			ret += dfs(b);
			chld[a].push_back(b);
		} 
	}
	if(v != -1) return ret;
	if((ret >= f[0].ff && n - ret >= f[1].ff) || (ret >= f[1].ff && n - ret >= f[0].ff)) v = a;
	if((ret >= f[1].ff && n - ret >= f[0].ff)) r = 1;
	return ret;
}

void coldfs(int a, int col){
	if(coln[col-1] == 0) return;
	res[a] = col;
	coln[col-1]--;
	for (auto b : chld[a]) {
		if(!res[b]){
			coldfs(b, col);
		}
	}
}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
	n = nn;
	f = {{a, 1}, {b, 2}, {c, 3}};
	coln = {a, b, c};
	adj.assign(n, {});
	chld.assign(n, {});
	vis.assign(n, 0);
	res.assign(n, 0);
	FOR(i, p.size()){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	sort(all(f));

	dfs(0);
	if(v == -1) return res;
	
	if(r) {
		coldfs(v, f[1].ss);
		coldfs(0, f[0].ss);
	}
	else{
		coldfs(v, f[0].ss);
		coldfs(0, f[1].ss);
	}
	FOR(i, n) if(res[i] == 0) res[i] = f[2].ss;

	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:12:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, n) for (int i = 0; i < n; i++)
......
   58 |  FOR(i, p.size()){
      |      ~~~~~~~~~~~                     
split.cpp:58:2: note: in expansion of macro 'FOR'
   58 |  FOR(i, p.size()){
      |  ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Correct 0 ms 344 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 604 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 52 ms 22352 KB ok, correct split
8 Correct 51 ms 19916 KB ok, correct split
9 Correct 48 ms 19272 KB ok, correct split
10 Correct 51 ms 22728 KB ok, correct split
11 Correct 58 ms 22520 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 67 ms 18948 KB ok, correct split
5 Correct 44 ms 13420 KB ok, correct split
6 Correct 63 ms 22608 KB ok, correct split
7 Correct 66 ms 19980 KB ok, correct split
8 Correct 66 ms 17080 KB ok, correct split
9 Correct 45 ms 14932 KB ok, correct split
10 Correct 32 ms 12108 KB ok, correct split
11 Correct 38 ms 12160 KB ok, correct split
12 Correct 33 ms 12632 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB ok, correct split
2 Correct 45 ms 13396 KB ok, correct split
3 Correct 16 ms 5468 KB ok, correct split
4 Correct 1 ms 344 KB ok, correct split
5 Correct 65 ms 17284 KB ok, correct split
6 Correct 54 ms 17200 KB ok, correct split
7 Correct 50 ms 17072 KB ok, correct split
8 Correct 48 ms 18256 KB ok, correct split
9 Correct 47 ms 16720 KB ok, correct split
10 Correct 19 ms 4680 KB ok, no valid answer
11 Correct 20 ms 6748 KB ok, no valid answer
12 Correct 36 ms 12892 KB ok, no valid answer
13 Correct 49 ms 13396 KB ok, no valid answer
14 Correct 32 ms 12628 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok, correct split
2 Correct 0 ms 344 KB ok, no valid answer
3 Correct 1 ms 544 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 344 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 1 ms 348 KB ok, correct split
8 Correct 0 ms 348 KB ok, correct split
9 Correct 2 ms 856 KB ok, correct split
10 Correct 2 ms 604 KB ok, correct split
11 Correct 0 ms 348 KB ok, correct split
12 Correct 2 ms 696 KB ok, correct split
13 Correct 0 ms 344 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 1 ms 348 KB ok, correct split
16 Correct 0 ms 344 KB ok, correct split
17 Correct 0 ms 344 KB ok, correct split
18 Correct 0 ms 348 KB ok, correct split
19 Correct 1 ms 348 KB ok, correct split
20 Correct 1 ms 348 KB ok, correct split
21 Correct 1 ms 856 KB ok, correct split
22 Correct 2 ms 604 KB ok, correct split
23 Correct 1 ms 860 KB ok, correct split
24 Correct 2 ms 604 KB ok, correct split
25 Correct 1 ms 696 KB ok, correct split
26 Incorrect 2 ms 604 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Correct 0 ms 344 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 604 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 52 ms 22352 KB ok, correct split
8 Correct 51 ms 19916 KB ok, correct split
9 Correct 48 ms 19272 KB ok, correct split
10 Correct 51 ms 22728 KB ok, correct split
11 Correct 58 ms 22520 KB ok, correct split
12 Correct 0 ms 348 KB ok, correct split
13 Correct 1 ms 348 KB ok, correct split
14 Correct 1 ms 348 KB ok, correct split
15 Correct 67 ms 18948 KB ok, correct split
16 Correct 44 ms 13420 KB ok, correct split
17 Correct 63 ms 22608 KB ok, correct split
18 Correct 66 ms 19980 KB ok, correct split
19 Correct 66 ms 17080 KB ok, correct split
20 Correct 45 ms 14932 KB ok, correct split
21 Correct 32 ms 12108 KB ok, correct split
22 Correct 38 ms 12160 KB ok, correct split
23 Correct 33 ms 12632 KB ok, correct split
24 Correct 0 ms 596 KB ok, correct split
25 Correct 45 ms 13396 KB ok, correct split
26 Correct 16 ms 5468 KB ok, correct split
27 Correct 1 ms 344 KB ok, correct split
28 Correct 65 ms 17284 KB ok, correct split
29 Correct 54 ms 17200 KB ok, correct split
30 Correct 50 ms 17072 KB ok, correct split
31 Correct 48 ms 18256 KB ok, correct split
32 Correct 47 ms 16720 KB ok, correct split
33 Correct 19 ms 4680 KB ok, no valid answer
34 Correct 20 ms 6748 KB ok, no valid answer
35 Correct 36 ms 12892 KB ok, no valid answer
36 Correct 49 ms 13396 KB ok, no valid answer
37 Correct 32 ms 12628 KB ok, no valid answer
38 Correct 1 ms 600 KB ok, correct split
39 Correct 0 ms 344 KB ok, no valid answer
40 Correct 1 ms 544 KB ok, correct split
41 Correct 0 ms 348 KB ok, correct split
42 Correct 0 ms 344 KB ok, correct split
43 Correct 0 ms 348 KB ok, correct split
44 Correct 1 ms 348 KB ok, correct split
45 Correct 0 ms 348 KB ok, correct split
46 Correct 2 ms 856 KB ok, correct split
47 Correct 2 ms 604 KB ok, correct split
48 Correct 0 ms 348 KB ok, correct split
49 Correct 2 ms 696 KB ok, correct split
50 Correct 0 ms 344 KB ok, correct split
51 Correct 0 ms 348 KB ok, correct split
52 Correct 1 ms 348 KB ok, correct split
53 Correct 0 ms 344 KB ok, correct split
54 Correct 0 ms 344 KB ok, correct split
55 Correct 0 ms 348 KB ok, correct split
56 Correct 1 ms 348 KB ok, correct split
57 Correct 1 ms 348 KB ok, correct split
58 Correct 1 ms 856 KB ok, correct split
59 Correct 2 ms 604 KB ok, correct split
60 Correct 1 ms 860 KB ok, correct split
61 Correct 2 ms 604 KB ok, correct split
62 Correct 1 ms 696 KB ok, correct split
63 Incorrect 2 ms 604 KB jury found a solution, contestant did not
64 Halted 0 ms 0 KB -