oj.uz

답안 #766936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766936 2023-06-26T09:10:15 Z khshg Split the Attractions (IOI19_split) C++14
18 / 100
 53 ms 11068 KB 
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
 
#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
 
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
 
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }

V<vi> adj;

struct DSU {
	vector<int> E;
	void init(int n) { E = vector<int>(n, -1); }
	int parent(int x) { return E[x] < 0 ? x : E[x] = parent(E[x]); }
	bool sameset(int x, int y) { return parent(x) == parent(y); }
	int size(int x) { return -E[parent(x)]; }
	bool unite(int x, int y) {
		x = parent(x);
		y = parent(y);
		if(x == y) {
			return false;
		}
		if(E[x] > E[y]) {
			swap(x, y);
		}
		E[x] += E[y];
		E[y] = x;
		return true;
	}
}D;

vi ans;

void color(int s, int& cnt, int c) {
	if(!cnt) return;
	--cnt;
	ans[s] = c;
	trav(u, adj[s]) {
		if(!cnt) break;
		if(ans[u] == 0) color(u, cnt, c);
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	D.init(N);
	ans = vi(N);
	adj.rsz(N);
	int M = sz(p);
	vpi comp;
	F0R(i, M) {
		if(!D.unite(p[i], q[i])) continue;
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	vi res;
	{
		set<int> t;
		F0R(i, N) {
			t.ins(D.parent(i));
		}
		trav(u, t) {
			comp.eb(D.size(u), u);
		}
		sor(comp);
	}
	int mn = min({a, b, c});
	int mn2 = a + b + c - mn - max({a, b, c});
	int mncolor = (a == mn ? 1 : (b == mn ? 2 : 3));
	int mn2color = (a == mn2 && mncolor != 1 ? 1 : (b == mn2 && mncolor != 2 ? 2 : 3)); // sus;
	if(comp.bk.ff >= mn + mn2) {
		F0R(i, N) {
			if(D.parent(i) == comp.bk.ss && sz(adj[i]) == 1) {
				color(i, mn, mncolor);
			}
		}
		F0R(i, N) {
			if(D.parent(i) == comp.bk.ss && ans[i] == 0) {
				color(i, mn2, mn2color);
			}
		}
		F0R(i, N) {
			if(ans[i] == 0) {
				ans[i] = 6 - mncolor - mn2color;//;
			}
		}
	}
	auto x = lb(all(comp), mp(mn, 0)), y = lb(all(comp), mp(mn2, 0));
	if(x != end(comp) && y != end(comp)) {
		if(x == y) {
			++y;
			if(y == end(comp)) {
				return ans;
			}
		}
		//
		color((*x).ss, mn, mncolor);
		color((*y).ss, mn2, mn2color);
		F0R(i, N) {
			if(ans[i] == 0) {
				ans[i] = 6 - mncolor - mn2color;//;
			}
		}
		return ans;
	}
	return ans;
}
/*
int main() {
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB ok, correct split
2 Correct 1 ms 212 KB ok, correct split
3 Correct 0 ms 300 KB ok, correct split
4 Correct 1 ms 212 KB ok, correct split
5 Correct 0 ms 212 KB ok, correct split
6 Correct 1 ms 212 KB ok, correct split
7 Correct 41 ms 10304 KB ok, correct split
8 Correct 39 ms 8820 KB ok, correct split
9 Correct 40 ms 10700 KB ok, correct split
10 Correct 37 ms 8776 KB ok, correct split
11 Correct 40 ms 10260 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB ok, correct split
2 Correct 1 ms 212 KB ok, correct split
3 Correct 1 ms 308 KB ok, correct split
4 Correct 44 ms 9804 KB ok, correct split
5 Correct 40 ms 8768 KB ok, correct split
6 Correct 37 ms 8652 KB ok, correct split
7 Correct 39 ms 11068 KB ok, correct split
8 Correct 53 ms 10512 KB ok, correct split
9 Correct 38 ms 8808 KB ok, correct split
10 Correct 33 ms 9092 KB ok, correct split
11 Correct 32 ms 9056 KB ok, correct split
12 Correct 33 ms 9104 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB ok, correct split
2 Incorrect 40 ms 9132 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB ok, correct split
2 Incorrect 0 ms 300 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB ok, correct split
2 Correct 1 ms 212 KB ok, correct split
3 Correct 0 ms 300 KB ok, correct split
4 Correct 1 ms 212 KB ok, correct split
5 Correct 0 ms 212 KB ok, correct split
6 Correct 1 ms 212 KB ok, correct split
7 Correct 41 ms 10304 KB ok, correct split
8 Correct 39 ms 8820 KB ok, correct split
9 Correct 40 ms 10700 KB ok, correct split
10 Correct 37 ms 8776 KB ok, correct split
11 Correct 40 ms 10260 KB ok, correct split
12 Correct 1 ms 212 KB ok, correct split
13 Correct 1 ms 212 KB ok, correct split
14 Correct 1 ms 308 KB ok, correct split
15 Correct 44 ms 9804 KB ok, correct split
16 Correct 40 ms 8768 KB ok, correct split
17 Correct 37 ms 8652 KB ok, correct split
18 Correct 39 ms 11068 KB ok, correct split
19 Correct 53 ms 10512 KB ok, correct split
20 Correct 38 ms 8808 KB ok, correct split
21 Correct 33 ms 9092 KB ok, correct split
22 Correct 32 ms 9056 KB ok, correct split
23 Correct 33 ms 9104 KB ok, correct split
24 Correct 1 ms 212 KB ok, correct split
25 Incorrect 40 ms 9132 KB 2 components are not connected
26 Halted 0 ms 0 KB -