oj.uz

Submission #285235

# Submission time Handle Problem Language Result Execution time Memory
285235 2020-08-28T12:55:50 Z cookiedoth Split the Attractions (IOI19_split) C++14
40 / 100
 134 ms 16376 KB 
/*

Code for problem B by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


СТРОИМ КОММУНИЗМ РАБОТЯГИ!
 
                                    ╦═╩═╦═╩═█
                          ████▄▄▄═╦═╩═╦═╩═╦═█
                  ████████████████▄▄╦═╩═╦═╩═█
█═╦═╩═╦▄████████████████▀▀▀▀█████████▄╦═╩═╦═█
█═╩═╦═████████████████████▄═╦▀█████████═╦═╩═█
█═╦═▄██████████▀╩═╦═╩▄██████▄═╦▀████████▄═╦═█
█═╩═█████████▀╩═╦═╩═█████████▄╩═╦████████═╩═█
█═╦█████████▄═╦═╩═╦═▀█████████╦═╩═████████╦═█
█═╩███████████▄▄██▄═╦═▀████████═╦═████████╩═█
█═██████████████████▄═╦═▀█████▀═╩═█████████═█
█═████████████████████▄═╦═▀███╩═╦═█████████═█
█═╦████████████▀╩▀██████▄═╦═▀═╦═╩█████████╦═█
█═╩█████████▀═╩═╦═╩▀▀███▀▀╩═╦═╩═██████████╩═█
█═╦═██████▀═╦═▄▄█▄▄═╩═╦═╩═╦═╩═╦═╩▀███████═╦═█
█═╩═▀████═╩═▄█████████▄▄▄▄████▄═╦═╩█████▀═╩═█
█═╦═╩═██████████████████████████▄═▄████═╩═╦═█
█═╩═╦═╩▀█████████████████████████████▀╩═╦═╩═█
█═╦═╩═╦═╩▀▀███████████████████████▀▀╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═▀▀▀███████████████▀▀▀═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═▀▀▀▀▀▀▀▀▀═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

=_=
¯\_(ツ)_/¯
o_O

*/

#include "split.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int mx = 1e5 + 228;
vector<vector<int> > g;
vector<int> ans;
int n, used[mx], a, b, c, timer;

void dfs(int v) {
	used[v] = 1;
	if (timer < b) {
		ans[v] = 2;
	} else {
		if (timer < a + b) {
			ans[v] = 1;
		} else {
			ans[v] = 3;
		}
	}
	timer++;
	for (auto v1 : g[v]) {
		if (used[v1] == 0) {
			dfs(v1);
		}
	}
}

void solve_dfs() {
	for (int i = 0; i < n; ++i) {
		if (g[i].size() == 1) {
			dfs(i);
			return;
		}
	}
	dfs(0);
}

int sz[mx], par[mx];

void dfs(int v, int pv) {
	par[v] = pv;
	sz[v] = 1;
	for (auto v1 : g[v]) {
		if (v1 != pv) {
			dfs(v1, v);
			sz[v] += sz[v1];
		}
	}
}

void build_cmp(int v, int pv, int &v_cnt, int clr) {
	v_cnt--;
	ans[v] = clr;
	for (auto v1 : g[v]) {
		if (v1 != pv && v_cnt) {
			build_cmp(v1, v, v_cnt, clr);
		}
	}
}

void solve_tree(int cur_a, int cur_b, int c1, int c2) {
	if (ans[0] != 0) {
		return;
	}
	dfs(0, 0);
	for (int i = 1; i < n; ++i) {
		if (sz[i] >= cur_a && (n - sz[i]) >= cur_b) {
			fill(all(ans), c1 ^ c2);
			build_cmp(i, par[i], cur_a, c1);
			build_cmp(par[i], i, cur_b, c2);
			return;
		}
		if (sz[i] >= cur_b && (n - sz[i]) >= cur_a) {
			fill(all(ans), c1 ^ c2);
			build_cmp(i, par[i], cur_b, c2);
			build_cmp(par[i], i, cur_a, c1);
			return;
		} 
	}
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n;
	a = _a;
	b = _b;
	c = _c;
	g.resize(n);
	int m = p.size();
	for (int i = 0; i < m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	ans.resize(n);
	if (m == n - 1) {
		solve_tree(a, b, 1, 2);
		solve_tree(a, c, 1, 3);
		solve_tree(b, c, 2, 3);
	} else {
		solve_dfs();
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 0 ms 384 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 104 ms 15992 KB ok, correct split
8 Correct 103 ms 16376 KB ok, correct split
9 Correct 99 ms 13688 KB ok, correct split
10 Correct 85 ms 12792 KB ok, correct split
11 Correct 88 ms 12792 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Correct 108 ms 12792 KB ok, correct split
5 Correct 88 ms 10232 KB ok, correct split
6 Correct 97 ms 12792 KB ok, correct split
7 Correct 104 ms 14072 KB ok, correct split
8 Correct 134 ms 13048 KB ok, correct split
9 Correct 83 ms 9720 KB ok, correct split
10 Correct 63 ms 10100 KB ok, correct split
11 Correct 76 ms 10096 KB ok, correct split
12 Correct 65 ms 10480 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB ok, correct split
2 Correct 89 ms 10236 KB ok, correct split
3 Correct 34 ms 4344 KB ok, correct split
4 Correct 0 ms 384 KB ok, correct split
5 Correct 113 ms 12152 KB ok, correct split
6 Correct 107 ms 12024 KB ok, correct split
7 Correct 97 ms 12024 KB ok, correct split
8 Correct 107 ms 12920 KB ok, correct split
9 Correct 115 ms 12024 KB ok, correct split
10 Correct 33 ms 3580 KB ok, no valid answer
11 Correct 38 ms 5248 KB ok, no valid answer
12 Correct 81 ms 10356 KB ok, no valid answer
13 Correct 94 ms 10232 KB ok, no valid answer
14 Correct 64 ms 10608 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB ok, correct split
2 Correct 0 ms 384 KB ok, correct split
3 Correct 1 ms 384 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 1 ms 384 KB ok, correct split
6 Correct 1 ms 384 KB ok, correct split
7 Correct 104 ms 15992 KB ok, correct split
8 Correct 103 ms 16376 KB ok, correct split
9 Correct 99 ms 13688 KB ok, correct split
10 Correct 85 ms 12792 KB ok, correct split
11 Correct 88 ms 12792 KB ok, correct split
12 Correct 1 ms 376 KB ok, correct split
13 Correct 0 ms 256 KB ok, correct split
14 Correct 1 ms 384 KB ok, correct split
15 Correct 108 ms 12792 KB ok, correct split
16 Correct 88 ms 10232 KB ok, correct split
17 Correct 97 ms 12792 KB ok, correct split
18 Correct 104 ms 14072 KB ok, correct split
19 Correct 134 ms 13048 KB ok, correct split
20 Correct 83 ms 9720 KB ok, correct split
21 Correct 63 ms 10100 KB ok, correct split
22 Correct 76 ms 10096 KB ok, correct split
23 Correct 65 ms 10480 KB ok, correct split
24 Correct 0 ms 384 KB ok, correct split
25 Correct 89 ms 10236 KB ok, correct split
26 Correct 34 ms 4344 KB ok, correct split
27 Correct 0 ms 384 KB ok, correct split
28 Correct 113 ms 12152 KB ok, correct split
29 Correct 107 ms 12024 KB ok, correct split
30 Correct 97 ms 12024 KB ok, correct split
31 Correct 107 ms 12920 KB ok, correct split
32 Correct 115 ms 12024 KB ok, correct split
33 Correct 33 ms 3580 KB ok, no valid answer
34 Correct 38 ms 5248 KB ok, no valid answer
35 Correct 81 ms 10356 KB ok, no valid answer
36 Correct 94 ms 10232 KB ok, no valid answer
37 Correct 64 ms 10608 KB ok, no valid answer
38 Incorrect 1 ms 256 KB 2 components are not connected
39 Halted 0 ms 0 KB -