oj.uz

Submission #986610

# Submission time Handle Problem Language Result Execution time Memory
986610 2024-05-20T21:11:52 Z mariaclara Split the Attractions (IOI19_split) C++17
11 / 100
 56 ms 10320 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)
	or (sub[x] >= B and sz(sub)-sub[x] >= A)) 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;
		int type = 1;
		if(n - sub[no] < B) type = 2;

		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] = type;
			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] = 3-type;
			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;
	}
}

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 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Incorrect 1 ms 344 KB invalid split: #1=20, #2=40, #3=40
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.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 348 KB ok, correct split
4 Correct 50 ms 8780 KB ok, correct split
5 Correct 37 ms 7760 KB ok, correct split
6 Correct 33 ms 7888 KB ok, correct split
7 Correct 43 ms 7772 KB ok, correct split
8 Correct 56 ms 10320 KB ok, correct split
9 Correct 38 ms 7768 KB ok, correct split
10 Correct 31 ms 8656 KB ok, correct split
11 Correct 33 ms 8660 KB ok, correct split
12 Correct 32 ms 8660 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Incorrect 41 ms 8788 KB invalid split: #1=21840, #2=20000, #3=58160
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, no valid answer
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 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 0 ms 348 KB ok, correct split
8 Correct 0 ms 348 KB ok, correct split
9 Correct 2 ms 724 KB ok, correct split
10 Incorrect 2 ms 604 KB invalid split: #1=100, #2=2367, #3=33
11 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 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Incorrect 1 ms 344 KB invalid split: #1=20, #2=40, #3=40
7 Halted 0 ms 0 KB -