oj.uz

답안 #950614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950614 2024-03-20T13:45:53 Z qin Split the Attractions (IOI19_split) C++17
0 / 100
 79 ms 19536 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct graph{
		vv<vv<int>> bg, g;
		vv<int> vis, sz, col;
		void init(int n){
				bg.resize(n), vis.resize(n), g.resize(n), sz.resize(n, 0), col.resize(n, 0);
		}
		void add_edge_b(int a, int b){ bg[a].emplace_back(b), bg[b].emplace_back(a); }
		void add_edge_g(int a, int b){ g[a].emplace_back(b), g[b].emplace_back(a); }
		void get_tree(int x){
				vis[x] = 1;
				for(int u : bg[x]) if(!vis[u]) add_edge_g(u, x), get_tree(u);
		}
		void dfs_sz(int x, int par){
				sz[x] = 1;
				for(int u : g[x]) if(u != par) dfs_sz(u, x), sz[x] += sz[u];
		}
		int find_centroid(int x, int par, int &n){
				int ret = x;
				for(int u : g[x]) if(u != par && sz[u] > n/2) ret = find_centroid(u, x, n);
				return ret;
		}
		void dfs_col(int x, int par, int k, int kol){
				col[x] = kol; --k;
				for(int u : g[x]) if(u != par && !col[u] && k){
						if(k <= sz[u]) dfs_col(u, x, k, kol), k = 0;
						else dfs_col(u, x, sz[u], kol), k -= sz[u];
				}
		}
};
vv<int> find_split(int n, int a, int b, int c, vv<int> p, vv<int> q){
		if(a > b) swap(a, b);
		if(b > c) swap(b, c);
		if(a > b) swap(a, b);
		int m = ssize(p);
		graph g; g.init(n);
		for(int i = 0; i < m; ++i) g.add_edge_b(p[i], q[i]);
		g.get_tree(0);
		g.dfs_sz(0, -1);
		int x = g.find_centroid(0, -1, n);
		g.dfs_sz(x, -1);
		bool good = 0;
		//~ printf("%d\n", x);
		for(int u : g.g[x]) if(a <= g.sz[u]){ g.dfs_col(u, x, a, 1), good = 1; break; }
		if(good){
				g.dfs_col(x, -1, b, 2);
				for(int i = 0; i < n; ++i) if(!g.col[i]) g.col[i] = 3;
		}
		return g.col;
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n, m, a, b, c; scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
				vv<int> p(m), q(m);
				for(int i = 0; i < m; ++i) scanf("%d%d", &p[i], &q[i]);
				vv<int> res = find_split(n, a, b, c, p, q);
				for(int u : res) printf("%d ", u);
				pn;
		}
		return 0;
}
#endif

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 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 408 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 408 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 75 ms 18980 KB ok, correct split
5 Correct 79 ms 15700 KB ok, correct split
6 Correct 58 ms 19536 KB ok, correct split
7 Incorrect 61 ms 18256 KB invalid split: #1=1, #2=49999, #3=50000
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB invalid split: #1=1, #2=2, #3=2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB invalid split: #1=2, #2=3, #3=4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 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 408 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -