oj.uz

Submission #986608

# Submission time Handle Problem Language Result Execution time Memory
986608 2024-05-20T21:06:59 Z mariaclara Split the Attractions (IOI19_split) C++17
18 / 100
 66 ms 15988 KB 
#include "split.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int A, B, no = -1, pai;
vector<int> sub, vis;
vector<vector<int>> edges;

void dfs(int x, int anc) {
	sub[x] = 1;
	vis[x] = 1;

	for(int viz : edges[x])
		if(!vis[viz]) dfs(viz, x), sub[x] += sub[viz];

	if(sub[x] >= A and sz(sub)-sub[x] >= B) no = x, pai = anc;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	edges.resize(n);

	for(int i = 0; i < sz(p); i++)
		edges[p[i]].pb(q[i]), edges[q[i]].pb(p[i]);

	if(a == 100) {
		queue<int> fila;
		vector<int> ans(n);
		fila.push(0);

		int cnt = 0;
		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(ans[x]) continue;
			ans[x] = 2;
			cnt++;
			if(cnt == b) break;

			for(int viz : edges[x])
				if(!ans[viz]) fila.push(viz);
		}

		for(int i = 0; i < n; i++)
			if(a and ans[i] == 0) ans[i] = 1, a = 0;
			else if(ans[i] == 0) ans[i] = 3;
		
		return ans;
	}
	else{
		sub.resize(n);
		vis.resize(n);
		
		A = min({a,b,c});
		B = min({max(a,b), max(b,c), max(c,a)});
		dfs(0, 0);

		vector<int> ans(n);
		if(no == -1) return ans;

		for(int i = 0; i < sz(edges[no]); i++) {
			if(edges[no][i] == pai) {
				edges[no].erase(edges[no].begin()+i);
				break;
			}
		}

		queue<int> fila;
		fila.push(no);
		int cnt = 0;
		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(ans[x]) continue;
			ans[x] = 1;
			cnt++;
			if(cnt == A) break;

			for(int viz : edges[x])
				if(!ans[viz]) fila.push(viz);
		}
		
		while(!fila.empty()) fila.pop();
		fila.push(pai);
		cnt = 0;

		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(ans[x]) continue;
			ans[x] = 2;
			cnt++;
			if(cnt == B) break;

			for(int viz : edges[x])
				if(!ans[viz]) fila.push(viz);
		}

		for(int i = 0; i < n; i++) {
			if(ans[i] == 1) {
				if(a > A and b == A) ans[i] = 2;
				else if(a > A) ans[i] = 3;
			}
			else if(ans[i] == 2) {
				if(a > A and a == B) ans[i] = 1;
				else if(b > B or (b == A and a > A)) ans[i] = 3;
			}
			else {
				if(a > B) ans[i] = 1;
				else if(b > B or (b > c and b >= a)) ans[i] = 2;
				else ans[i] = 3;
			}
		}

		return ans;
	}
}

/*
5 5
2 2 1
1 4
4 0
0 3
3 2
2 1
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 66 ms 14420 KB ok, correct split
8 Correct 42 ms 12628 KB ok, correct split
9 Correct 43 ms 12116 KB ok, correct split
10 Correct 43 ms 15988 KB ok, correct split
11 Correct 49 ms 15956 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 53 ms 12620 KB ok, correct split
5 Correct 40 ms 8528 KB ok, correct split
6 Correct 45 ms 14676 KB ok, correct split
7 Correct 44 ms 12380 KB ok, correct split
8 Correct 66 ms 11088 KB ok, correct split
9 Correct 43 ms 8628 KB ok, correct split
10 Correct 36 ms 9672 KB ok, correct split
11 Correct 33 ms 9428 KB ok, correct split
12 Correct 33 ms 9420 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Incorrect 38 ms 8632 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 0 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, no valid answer
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 1 ms 348 KB ok, correct split
8 Correct 1 ms 348 KB ok, correct split
9 Correct 2 ms 604 KB ok, correct split
10 Correct 2 ms 604 KB ok, correct split
11 Correct 1 ms 344 KB ok, correct split
12 Incorrect 2 ms 708 KB invalid split: #1=800, #2=1601, #3=0
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 66 ms 14420 KB ok, correct split
8 Correct 42 ms 12628 KB ok, correct split
9 Correct 43 ms 12116 KB ok, correct split
10 Correct 43 ms 15988 KB ok, correct split
11 Correct 49 ms 15956 KB ok, correct split
12 Correct 1 ms 348 KB ok, correct split
13 Correct 0 ms 348 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 53 ms 12620 KB ok, correct split
16 Correct 40 ms 8528 KB ok, correct split
17 Correct 45 ms 14676 KB ok, correct split
18 Correct 44 ms 12380 KB ok, correct split
19 Correct 66 ms 11088 KB ok, correct split
20 Correct 43 ms 8628 KB ok, correct split
21 Correct 36 ms 9672 KB ok, correct split
22 Correct 33 ms 9428 KB ok, correct split
23 Correct 33 ms 9420 KB ok, correct split
24 Correct 0 ms 344 KB ok, correct split
25 Incorrect 38 ms 8632 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -