oj.uz

답안 #926512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926512 2024-02-13T07:44:39 Z GrindMachine Split the Attractions (IOI19_split) C++17
11 / 100
 2000 ms 20712 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<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());

	rep(iter,4000){
		shuffle(all(edges),rng);
		rep(i,n) adj2[i].clear();
		DSU dsu(n);
		for(auto [u,v] : edges){
			if(!dsu.same(u,v)){
				dsu.merge(u,v);
				adj2[u].pb(v), adj2[v].pb(u);
			}
		}

		ans = vector<int>(n,0);
		dfs1(0,-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(0,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 3;
						}
					}
				}
				else{
					to_col = {3,C};
					dfs2(0,-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(0,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 3;
						}
					}
				}
				else{
					to_col = {3,C};
					dfs2(0,-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(0,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 2;
						}
					}
				}
				else{
					to_col = {2,B};
					dfs2(0,-1);
					rep(i,n){
						if(!ans[i]){
							ans[i] = 1;
						}
					}
				}

				return ans;
			}
		}
	}

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5720 KB ok, correct split
3 Correct 1 ms 5976 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 1 ms 5720 KB ok, correct split
7 Correct 56 ms 20712 KB ok, correct split
8 Correct 52 ms 19400 KB ok, correct split
9 Incorrect 54 ms 19108 KB invalid split: #1=50001, #2=49999, #3=0
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5888 KB ok, correct split
3 Correct 2 ms 5724 KB ok, correct split
4 Correct 65 ms 17820 KB ok, correct split
5 Correct 52 ms 16520 KB ok, correct split
6 Correct 53 ms 19656 KB ok, correct split
7 Correct 55 ms 19348 KB ok, correct split
8 Correct 76 ms 19208 KB ok, correct split
9 Correct 56 ms 16328 KB ok, correct split
10 Correct 45 ms 17224 KB ok, correct split
11 Correct 44 ms 17520 KB ok, correct split
12 Correct 43 ms 17136 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5720 KB ok, correct split
2 Correct 56 ms 16580 KB ok, correct split
3 Correct 20 ms 10208 KB ok, correct split
4 Correct 2 ms 5724 KB ok, correct split
5 Correct 55 ms 17832 KB ok, correct split
6 Correct 54 ms 17692 KB ok, correct split
7 Correct 54 ms 17608 KB ok, correct split
8 Correct 57 ms 18376 KB ok, correct split
9 Correct 64 ms 17604 KB ok, correct split
10 Execution timed out 2056 ms 9428 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 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 1 ms 5724 KB ok, correct split
6 Correct 2 ms 5724 KB ok, correct split
7 Correct 1 ms 5724 KB ok, correct split
8 Correct 2 ms 5720 KB ok, correct split
9 Correct 3 ms 6232 KB ok, correct split
10 Correct 3 ms 6236 KB ok, correct split
11 Correct 1 ms 5724 KB ok, correct split
12 Incorrect 630 ms 6248 KB jury found a solution, contestant did not
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5724 KB ok, correct split
2 Correct 1 ms 5720 KB ok, correct split
3 Correct 1 ms 5976 KB ok, correct split
4 Correct 1 ms 5724 KB ok, correct split
5 Correct 2 ms 5724 KB ok, correct split
6 Correct 1 ms 5720 KB ok, correct split
7 Correct 56 ms 20712 KB ok, correct split
8 Correct 52 ms 19400 KB ok, correct split
9 Incorrect 54 ms 19108 KB invalid split: #1=50001, #2=49999, #3=0
10 Halted 0 ms 0 KB -