oj.uz

Submission #926517

# Submission time Handle Problem Language Result Execution time Memory
926517 2024-02-13T07:58:50 Z GrindMachine Split the Attractions (IOI19_split) C++17
18 / 100
 2000 ms 21128 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);
	}
}

vector<bool> vis(N);

void spanning_tree(int u){
	vis[u] = 1;
	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});
	}

	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	ans.resize(n);

	rep(root,n){
		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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 2 ms 5720 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 66 ms 19672 KB ok, correct split
8 Correct 49 ms 18376 KB ok, correct split
9 Correct 49 ms 17872 KB ok, correct split
10 Correct 49 ms 20940 KB ok, correct split
11 Correct 58 ms 21128 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 64 ms 18884 KB ok, correct split
5 Correct 68 ms 15504 KB ok, correct split
6 Correct 50 ms 19948 KB ok, correct split
7 Correct 49 ms 18128 KB ok, correct split
8 Correct 68 ms 17852 KB ok, correct split
9 Correct 72 ms 15304 KB ok, correct split
10 Correct 40 ms 16080 KB ok, correct split
11 Correct 43 ms 15916 KB ok, correct split
12 Correct 39 ms 15944 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 49 ms 15304 KB ok, correct split
3 Correct 18 ms 9680 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 53 ms 16700 KB ok, correct split
6 Correct 49 ms 16584 KB ok, correct split
7 Correct 49 ms 16584 KB ok, correct split
8 Correct 70 ms 17336 KB ok, correct split
9 Correct 50 ms 16472 KB ok, correct split
10 Execution timed out 2045 ms 8916 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5976 KB ok, no valid answer
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 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 2 ms 5720 KB ok, correct split
8 Correct 1 ms 5724 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 2 ms 5720 KB ok, correct split
14 Correct 2 ms 5724 KB ok, correct split
15 Correct 2 ms 5724 KB ok, correct split
16 Correct 2 ms 5720 KB ok, correct split
17 Correct 1 ms 5948 KB ok, correct split
18 Correct 1 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 6236 KB ok, correct split
22 Correct 2 ms 5980 KB ok, correct split
23 Correct 3 ms 6236 KB ok, correct split
24 Correct 2 ms 6236 KB ok, correct split
25 Correct 2 ms 6236 KB ok, correct split
26 Incorrect 112 ms 6236 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 2 ms 5724 KB ok, correct split
3 Correct 1 ms 5724 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 2 ms 5720 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 66 ms 19672 KB ok, correct split
8 Correct 49 ms 18376 KB ok, correct split
9 Correct 49 ms 17872 KB ok, correct split
10 Correct 49 ms 20940 KB ok, correct split
11 Correct 58 ms 21128 KB ok, correct split
12 Correct 1 ms 5724 KB ok, correct split
13 Correct 1 ms 5724 KB ok, correct split
14 Correct 1 ms 5724 KB ok, correct split
15 Correct 64 ms 18884 KB ok, correct split
16 Correct 68 ms 15504 KB ok, correct split
17 Correct 50 ms 19948 KB ok, correct split
18 Correct 49 ms 18128 KB ok, correct split
19 Correct 68 ms 17852 KB ok, correct split
20 Correct 72 ms 15304 KB ok, correct split
21 Correct 40 ms 16080 KB ok, correct split
22 Correct 43 ms 15916 KB ok, correct split
23 Correct 39 ms 15944 KB ok, correct split
24 Correct 2 ms 5720 KB ok, correct split
25 Correct 49 ms 15304 KB ok, correct split
26 Correct 18 ms 9680 KB ok, correct split
27 Correct 1 ms 5724 KB ok, correct split
28 Correct 53 ms 16700 KB ok, correct split
29 Correct 49 ms 16584 KB ok, correct split
30 Correct 49 ms 16584 KB ok, correct split
31 Correct 70 ms 17336 KB ok, correct split
32 Correct 50 ms 16472 KB ok, correct split
33 Execution timed out 2045 ms 8916 KB Time limit exceeded
34 Halted 0 ms 0 KB -