oj.uz

Submission #986606

# Submission time Handle Problem Language Result Execution time Memory
986606 2024-05-20T20:54:32 Z mariaclara Split the Attractions (IOI19_split) C++17
11 / 100
 58 ms 12548 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 == 1) {
		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) ans[i] = 3;
			}
			else {
				if(a > B) ans[i] = 1;
				else if(b > B) ans[i] = 2;
				else ans[i] = 3;
			}
		}

		return ans;
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 344 KB ok, correct split
4 Incorrect 0 ms 436 KB invalid split: #1=2, #2=2, #3=0
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 58 ms 10580 KB ok, correct split
5 Correct 38 ms 9160 KB ok, correct split
6 Correct 42 ms 9152 KB ok, correct split
7 Correct 35 ms 8788 KB ok, correct split
8 Correct 58 ms 12548 KB ok, correct split
9 Correct 36 ms 8028 KB ok, correct split
10 Correct 32 ms 9424 KB ok, correct split
11 Correct 33 ms 9428 KB ok, correct split
12 Correct 36 ms 9624 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB ok, correct split
2 Incorrect 38 ms 9812 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 Incorrect 0 ms 348 KB invalid split: #1=4, #2=5, #3=0
2 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 348 KB ok, correct split
3 Correct 0 ms 344 KB ok, correct split
4 Incorrect 0 ms 436 KB invalid split: #1=2, #2=2, #3=0
5 Halted 0 ms 0 KB -