Submission #1278246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278246		al95ireyiz	Split the Attractions (IOI19_split)	C++20	0 / 100	2094 ms	14224 KiB

split

#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 1e5 + 5;

ll n, m, k = 0;

vll g[maxn];
vector<int>cv;
ll a, b, c, cal[4];
bitset<maxn>vis;
ll dfs(ll u){
    vis[u] = 1;
    ll cv = 1;
    for(auto v : g[u]){
        if(vis[v]) continue;
        cv += dfs(v);
    }
    return cv;
}
void dfs2(ll u){
    vis[u] = 1;
    cv[u - 1] = 1;
    a --;
    if(a == 0) return;
    for(auto v : g[u]){
        if(vis[v]) continue;
        dfs2(v);
        if(a == 0) return;
    }
}
void dfs3(ll u){
    vis[u] = 1;
    cv[u - 1] = 2;
    b --;
    if(b == 0) return;
    for(auto v : g[u]){
        if(vis[v]) continue;
        dfs3(v);
        if(b == 0) return;
    }
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n, a = _a, b = _b, c = _c;
    cal[1] = 1, cal[2] = 2, cal[3] = 3;
    if(a > b) swap(a, b), swap(cal[1], cal[2]);
    if(a > c) swap(a, c), swap(cal[1], cal[3]);
    if(b > c) swap(b, c), swap(cal[2], cal[3]);
    cv.assign(n, 3);
    for(ll i = 0; i < len(p); i ++){
        g[p[i] + 1].pb(q[i] + 1);
        g[q[i] + 1].pb(p[i] + 1);
    }
    ll ch = 0;
    pll tp;
    set<ll>s;
    for(ll __ = 1; __ <= n; __ ++){
        ll root = rand() % n + 1;
        while(s.count(root) and len(s) <= n) root = rand() % n + 1;
        s.in(root);

        vis.reset();
        vis[root] = 1;
        for(auto i : g[root]){
            ll le = dfs(i);
            if(le >= a and n - le >= b){
                ch = 1;
                tp = {i, root};
                break;
            }
        }
        if(ch) break;
        if(len(s) == n) break;
    }
    if(!ch){
        for(ll i = 0; i <= n - 1; i ++) cv[i] = 0;
        return cv;
    }
    vis.reset();
    auto [node, root] = tp;
    vis[root] = 1;
    dfs2(node);
    vis[root] = 0;
    dfs3(root);
    for(ll i = 0; i <= n - 1; i ++){
        cv[i] = cal[cv[i]];
    }
    return cv;
}
// void _() {
    
// }
// signed main() {
//     ll tm = clock();
//     cin.tie(0)->sync_with_stdio(0);
//     ll t = 1;
//     // cin >> t;
//     for(ll tt = 1; tt <= t; tt ++) _();
//     cerr << "\n\033[1;31mTime: \033[1;30m" \
//         << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
// }

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36