oj.uz

Submission #926515

# Submission time Handle Problem Language Result Execution time Memory
926515 2024-02-13T07:51:29 Z GrindMachine Split the Attractions (IOI19_split) C++17
11 / 100
 2000 ms 19760 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){
	assert(to_col.ss >= 0);
	
	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 = {1,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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 1 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 52 ms 19760 KB ok, correct split
8 Correct 47 ms 18376 KB ok, correct split
9 Incorrect 50 ms 17864 KB invalid split: #1=50001, #2=49999, #3=0
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory 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 18892 KB ok, correct split
5 Correct 46 ms 15308 KB ok, correct split
6 Correct 65 ms 19760 KB ok, correct split
7 Correct 50 ms 18116 KB ok, correct split
8 Correct 67 ms 17992 KB ok, correct split
9 Correct 45 ms 15248 KB ok, correct split
10 Correct 39 ms 15932 KB ok, correct split
11 Correct 39 ms 15932 KB ok, correct split
12 Correct 37 ms 15932 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 46 ms 15304 KB ok, correct split
3 Correct 18 ms 9684 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 54 ms 16840 KB ok, correct split
6 Correct 49 ms 16580 KB ok, correct split
7 Correct 54 ms 16384 KB ok, correct split
8 Correct 47 ms 17348 KB ok, correct split
9 Correct 48 ms 16328 KB ok, correct split
10 Execution timed out 2021 ms 8912 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB ok, correct split
2 Correct 2 ms 5724 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 5720 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 1 ms 5720 KB ok, correct split
8 Correct 2 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 5724 KB ok, correct split
12 Correct 3 ms 6236 KB ok, correct split
13 Correct 2 ms 5720 KB ok, correct split
14 Incorrect 2 ms 5724 KB invalid split: #1=7, #2=3, #3=0
15 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5724 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 2 ms 5720 KB ok, correct split
5 Correct 1 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 52 ms 19760 KB ok, correct split
8 Correct 47 ms 18376 KB ok, correct split
9 Incorrect 50 ms 17864 KB invalid split: #1=50001, #2=49999, #3=0
10 Halted 0 ms 0 KB -