oj.uz

답안 #926520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926520 2024-02-13T08:01:12 Z GrindMachine Split the Attractions (IOI19_split) C++17
18 / 100
 2000 ms 21464 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "split.h"

struct DSU {
    vector<int> par, rankk, siz;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
    }
};

vector<int> adj1[N], adj2[N];
vector<int> subsiz(N);
vector<int> par(N);

void dfs1(int u, int p){
	subsiz[u] = 1;
	par[u] = p;
	trav(v,adj2[u]){
		if(v == p) conts;
		dfs1(v,u);
		subsiz[u] += subsiz[v];
	}
}

pii to_col;
vector<int> ans;

void dfs2(int u, int p){
	if(!to_col.ss) return;
	to_col.ss--;
	ans[u] = to_col.ff;

	trav(v,adj2[u]){
		if(v == p) conts;
		if(ans[v]) conts;
		dfs2(v,u);
	}
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bool> vis(N);

void spanning_tree(int u){
	vis[u] = 1;
	shuffle(all(adj1[u]),rng);
	
	trav(v,adj1[u]){
		if(vis[v]) conts;
		adj2[u].pb(v), adj2[v].pb(u);
		spanning_tree(v);
	}
}

vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
	vector<pii> edges;
	rep(i,sz(p)){
		int u = p[i], v = q[i];
		adj1[u].pb(v), adj1[v].pb(u);
		edges.pb({u,v});
	}

	uniform_int_distribution dist(0,n-1);
	ans.resize(n);

	rep(iter,3000){
		ll root = dist(rng);
		rep(i,n){
			adj2[i].clear();
			vis[i] = 0;
		}

		spanning_tree(root);
		dfs1(root,-1);

		rep(u,n){
			int s = subsiz[u];
			
			if(s >= A and n-s >= min(B,C)){
				to_col = {1,A};
				dfs2(u,par[u]);

				if(B < C){
					to_col = {2,B};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 3;
						}
					}
				}
				else{
					to_col = {3,C};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 2;
						}
					}
				}

				return ans;
			}
			
			if(s >= B and n-s >= min(A,C)){
				to_col = {2,B};
				dfs2(u,par[u]);

				if(A < C){
					to_col = {1,A};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 3;
						}
					}
				}
				else{
					to_col = {3,C};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 1;
						}
					}
				}

				return ans;
			}

			if(s >= C and n-s >= min(A,B)){
				to_col = {3,C};
				dfs2(u,par[u]);

				if(A < B){
					to_col = {1,A};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 2;
						}
					}
				}
				else{
					to_col = {2,B};
					dfs2(root,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 1;
						}
					}
				}

				return ans;
			}
		}
	}

	return vector<int>(n,0);
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5720 KB ok, correct split
2 Correct 2 ms 5720 KB ok, correct split
3 Correct 2 ms 5720 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 56 ms 19360 KB ok, correct split
8 Correct 56 ms 20164 KB ok, correct split
9 Correct 53 ms 19636 KB ok, correct split
10 Correct 53 ms 21456 KB ok, correct split
11 Correct 61 ms 21464 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5724 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 67 ms 19652 KB ok, correct split
5 Correct 53 ms 15304 KB ok, correct split
6 Correct 56 ms 21432 KB ok, correct split
7 Correct 56 ms 19912 KB ok, correct split
8 Correct 96 ms 17832 KB ok, correct split
9 Correct 50 ms 15300 KB ok, correct split
10 Correct 45 ms 15936 KB ok, correct split
11 Correct 57 ms 15936 KB ok, correct split
12 Correct 47 ms 16060 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 51 ms 15532 KB ok, correct split
3 Correct 19 ms 9680 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 54 ms 17856 KB ok, correct split
6 Correct 58 ms 16836 KB ok, correct split
7 Correct 53 ms 16836 KB ok, correct split
8 Correct 56 ms 17592 KB ok, correct split
9 Correct 55 ms 17336 KB ok, correct split
10 Execution timed out 2052 ms 8912 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5720 KB ok, no valid answer
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 2 ms 5968 KB ok, correct split
6 Correct 1 ms 5724 KB ok, correct split
7 Correct 1 ms 5724 KB ok, correct split
8 Correct 1 ms 5720 KB ok, correct split
9 Correct 3 ms 6236 KB ok, correct split
10 Correct 3 ms 6236 KB ok, correct split
11 Correct 2 ms 5980 KB ok, correct split
12 Correct 3 ms 6236 KB ok, correct split
13 Correct 1 ms 5724 KB ok, correct split
14 Correct 1 ms 5724 KB ok, correct split
15 Correct 1 ms 5724 KB ok, correct split
16 Correct 1 ms 5724 KB ok, correct split
17 Correct 2 ms 5724 KB ok, correct split
18 Correct 2 ms 5724 KB ok, correct split
19 Correct 2 ms 5980 KB ok, correct split
20 Correct 2 ms 5980 KB ok, correct split
21 Correct 3 ms 6232 KB ok, correct split
22 Correct 3 ms 6232 KB ok, correct split
23 Correct 3 ms 6236 KB ok, correct split
24 Correct 3 ms 6164 KB ok, correct split
25 Correct 3 ms 5980 KB ok, correct split
26 Incorrect 485 ms 6268 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5720 KB ok, correct split
2 Correct 2 ms 5720 KB ok, correct split
3 Correct 2 ms 5720 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 56 ms 19360 KB ok, correct split
8 Correct 56 ms 20164 KB ok, correct split
9 Correct 53 ms 19636 KB ok, correct split
10 Correct 53 ms 21456 KB ok, correct split
11 Correct 61 ms 21464 KB ok, correct split
12 Correct 1 ms 5724 KB ok, correct split
13 Correct 2 ms 5724 KB ok, correct split
14 Correct 1 ms 5724 KB ok, correct split
15 Correct 67 ms 19652 KB ok, correct split
16 Correct 53 ms 15304 KB ok, correct split
17 Correct 56 ms 21432 KB ok, correct split
18 Correct 56 ms 19912 KB ok, correct split
19 Correct 96 ms 17832 KB ok, correct split
20 Correct 50 ms 15300 KB ok, correct split
21 Correct 45 ms 15936 KB ok, correct split
22 Correct 57 ms 15936 KB ok, correct split
23 Correct 47 ms 16060 KB ok, correct split
24 Correct 2 ms 5724 KB ok, correct split
25 Correct 51 ms 15532 KB ok, correct split
26 Correct 19 ms 9680 KB ok, correct split
27 Correct 2 ms 5724 KB ok, correct split
28 Correct 54 ms 17856 KB ok, correct split
29 Correct 58 ms 16836 KB ok, correct split
30 Correct 53 ms 16836 KB ok, correct split
31 Correct 56 ms 17592 KB ok, correct split
32 Correct 55 ms 17336 KB ok, correct split
33 Execution timed out 2052 ms 8912 KB Time limit exceeded
34 Halted 0 ms 0 KB -