Submission #1279407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279407		huyngodzz	Split the Attractions (IOI19_split)	C++20	29 / 100	44 ms	16692 KiB

split

///huynhocute123///
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = b; i >= a; --i)
#define ALL(v) v.begin(),v.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//random_device rd;
//mt19937 rng(rd());
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
const int MAX = 1e9+9;
const long long  MAXLL = 1e18+9;
const double pi = 3.14159265358979323846;
const double rad = 3.14159265358979323846 /180;
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return 1;
    }
    return 0;
}
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return 1;
    }
    return 0;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return 1;
    }
    return 0;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return 1;
    }
    return 0;
}
const int  mod = 1e9 + 7;
inline int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
inline void Add(int& x ,int y){
    x += y;
    if(x >= mod)x -=mod;
}
inline void Sub(int& x, int y){
    x-= y;
    if(x < 0)x += mod;
}
const int maxN = 1e5 + 99 ;
vector<pii> kk;
int n , m;
vector<int> e[maxN];
namespace Tree{
    bool check(){
        return (m <= n);
    }
    int sz[maxN], color[maxN];
    int mn;
    int flag;
    void Fill(int u ,int p, int idx){
        if(kk[idx].F <= 0)return;
//        cerr << u << " " << kk[idx].S << '\n';
        color[u] = kk[idx].S;
        --kk[idx].F;
        for(auto x : e[u]){
            if(x ==p )continue;
            Fill(x ,u , idx);
        }
    }
    void dfs(int u ,int p){
        if(flag == 1)return;
//        cerr << flag << " ";
        sz[u] = 1;
        for(auto x : e[u]){
            if(x == p)continue;
            dfs(x, u);
            sz[u] += sz[x];
        }
        if(flag)return;
        if(sz[u] >= kk[0].F){
            if(n - sz[u] >= kk[0].F){
                if(sz[u]  >= kk[1].F){
//                    cerr <<1 << " "<< u << " " << p << '\n';
                    Fill(u ,p, 1);
                    Fill(p, u , 0);
                    flag = 1;
//                    cerr << flag << " ";
                    return;
                }else if(n - sz[u] >= kk[1].F){
//                    cerr << u << " " << p << '\n';
                    Fill(u ,p, 0);
                    Fill(p, u , 1);
                    flag = 1;
                    return;
                }else assert(0);
                return;
            }

        }
    }
    vector<int> solve(){
        flag =0;
        dfs(0, -1);
        vector<int> ans;
        if(flag == 0){
                FOR(i, 0, n - 1)ans.pb(0);
        }
        else{
            FOR(i, 0, n - 1 ){
                if(color[i] == 0)ans.pb(kk[2].S);
                else ans.pb(color[i]);
            }
        }
        return ans;
    }
}
int lab[maxN];
int Find(int u){
    return  u== lab[u] ? u : lab[u] = Find(lab[u]);
}
bool Merge(int u ,int v){
    u = Find(u);
    v = Find(v);
    if(u == v)return 0;
    lab[v] = u;
    return 1;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    n = N;
    FOR(i, 1, n)lab[i] = i;
    kk.pb({a, 1});
    kk.pb({b, 2});
    kk.pb({c, 3});
    m = p.size();
    sort(ALL(kk));
    for(int i = 0 ; i < p.size(); i++){
        int u = p[i], v = q[i];
        if(Merge(u ,v)){
            e[u].pb(v);
            e[v].pb(u);
        }
    }
    if(Tree::check())return Tree::solve();
    vector<int>ans;
    FOR(i, 1 , n)ans.pb(0);
    return ans;
}
//
//inline void solve(){
//    cin >> n >> m;
//    FOR(i, 1, n)lab[i] = i;
//    FOR(i, 1, 3){
//        int x;cin >> x;
//        kk.pb({x, i});
//    }
//    sort(ALL(kk));
//    FOR(i, 1, m){
//        int u ,v;cin >> u >> v;
//        if(Merge(u ,v)){
////            cerr << u << " "<<v << "ADD \n";
//            e[u].pb(v);
//            e[v].pb(u);
//        }
//    }
//    if(!Tree::check()){
//            FOR(i, 1 ,n)cout << 0 << " ";
//            return;
//    }
//
//    vector<int> ans = Tree::solve();
//    for(auto x : ans)cout << x << " ";
//}
//#define NAME "task"
//signed main(){
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    if(fopen(NAME".inp", "r")){
//        freopen(NAME".inp", "r" ,stdin);
////        freopen(NAME".out", "w" ,stdout);
//    }
//    int tc = 1;
//   // cin >> tc;
//    while( tc-- )solve();
//    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
//
//
//}

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