제출 #1286167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286167		al95ireyiz	Split the Attractions (IOI19_split)	C++20	0 / 100	2094 ms	16372 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;

mt19937 rng(clock());
vll g[maxn];
ll sz[maxn];
bitset<maxn>vis;
void dfs(ll u, ll par = -1){
    vis[u] = 1;
    sz[u] ++;
    for(auto v : g[u]){
        if(vis[v]) continue;
        dfs(v);
        sz[u] += sz[v];
    }
}
void fill(ll u, vll &ve, ll &le){
    vis[u] = 1;
    ve.pb(u);
    if(len(ve) == le) return;
    for(auto v : g[u]){
        if(!vis[v]){
            fill(v, ve, le);
            if(len(ve) == le) return;
        }
    }
}
pair<vll, vll> f(ll x, ll y){
    if(x > y) swap(x, y);
    // 22 balliq subtask: tree-di

    // bir noqteden dfs atib baxa bilerem ki, subtreelerin arasinda ele v subtreesi varmi ki, sz[v] >= x ve n - sz[v] >= y 
    set<ll>s;
    for(ll __ = 0; __ <= 1000; __ ++){
        ll r = rng() % n;
        if(s.find(r) != s.end()) continue;
        s.in(r);
        for(ll i = 0; i < n; i ++) vis[i] = sz[i] = 0;
        
        vll a, b;
        dfs(r);
        vis.reset();
        
        for(auto ch : g[r]){
            if(sz[ch] >= x and n - sz[ch] >= y){
                vis[r] = 1;
                fill(ch, a, x);
                vis[r] = 0;
                for(auto och : g[r]){
                    if(ch == och) continue;
                    fill(och, b, y);
                }
                return {a, b};
            }
            if(sz[ch] >= y and n - sz[ch] >= x){
                vis[r] = 1;
                fill(ch, b, y);
                vis[r] = 0;
                for(auto och : g[r]){
                    if(ch == och) continue;
                    fill(och, a, x);
                }
                return {a, b};
            }
        }
    }
    return {{}, {}};
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q){
    n = _n;
    for(ll i = 0; i < n; i ++) g[i].clear();
    for(ll i = 0; i < len(p); i ++){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    vector<int>cv(n);
    if(_a <= _c and _b <= _c){
        auto [av, bv] = f(_a, _b);
        if(_a > _b) swap(av, bv);
        if(len(av) != _a) return cv;
        for(ll i = 0; i < n; i ++) cv[i] = 3;
        for(auto i : av) cv[i] = 1;
        for(auto i : bv) cv[i] = 2;
        return cv;
    }
    if(_a <= _b and _c <= _b){
        auto [av, _cv] = f(_a, _c);
        if(_a > _c) swap(av, _cv);
        if(len(av) != _a) return cv;
        for(ll i = 0; i < n; i ++) cv[i] = 2;
        for(auto i : av) cv[i] = 1;
        for(auto i : _cv) cv[i] = 3;
        return cv;
    }
    if(_b <= _a and _c <= _a){
        auto [bv, _cv] = f(_b, _c);
        if(_b > _c) swap(bv, _cv);
        if(len(bv) != _b) return cv;
        for(ll i = 0; i < n; i ++) cv[i] = 1;
        for(auto i : bv) cv[i] = 2;
        for(auto i : _cv) cv[i] = 3;
        return cv;
    }
    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