제출 #1108283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108283		underwaterkillerwhale	Split the Attractions (IOI19_split)	C++17	40 / 100	86 ms	42028 KiB

split

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9 + 7;
const int BASE = 137;
const int szBL = 350;

int n, m, A, B, C;
vector<int> ke[N];

namespace sub1 {
    bool check () {
        if (m > n) return 0;
        rep (u, 1, n) if (SZ(ke[u]) > 2) return 0;
        return 1;
    }

    vector<int> solution () {
        vector<int> Ans(n + 2, 0), dd(n + 2, 0);
        function<void(int, int)> dfs = [&] (int u, int p) {
            static int time_dfs = 0;
            ++time_dfs;
            if (time_dfs <= A) Ans[u] = 1;
            else if (time_dfs <= A + B) Ans[u] = 2;
            else Ans[u] = 3;
            dd[u] = 1;
            iter (&v, ke[u]) {
                if (v == p || dd[v]) continue;
                dfs(v, u);
            }
        };
        dfs(1, 0);
//        rep (i, 1, n) cout << Ans[i] <<" ";
        vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
        return subAns;
    }
}
namespace sub2 {
    bool check () {
        return A == 1;
    }
    vector<int> solution()  {
        vector<vector<int>> adj(n + 3);
        vector<int> deg(n + 3, 0), dd(n + 3, 0);
        function<void(int)> dfs = [&] (int u) {
            dd[u] = 1;
            iter (&v, ke[u]) {
                if (dd[v]) continue;
                adj[u].pb(v);
                adj[v].pb(u);
                dfs(v);
            }
        };
        dfs(1);
        queue<int> Q;
        rep (u, 1, n) {
            deg[u] = SZ(adj[u]);
            if (deg[u] == 1) {
                Q.push(u);
            }
        }
        vector<int> Ans(n + 3, 2);
        int step = 0;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            ++step;
            if (step <= A) Ans[u] = 1;
            else if (step <= A + C) Ans[u] = 3;
            deg[u] = -1;
            iter (&v, adj[u]) {
                --deg[v];
                if (deg[v] == 1) Q.push(v);
            }
        }
//        rep (i, 1, n) cout << Ans[i] <<" ";
        vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
        return subAns;
    }
}

namespace sub3 {
    bool check () {
        return m == n - 1;
    }
    vector<int> solution () {
        int idA, idB, idC; { ///màu gốc của màu A
            vector<pii> vec = { MP(A, 1), MP(B, 2), MP(C, 3) };
            sort (ALL(vec));
            tie(A, idA) = vec[0], tie(B, idB) = vec[1], tie(C, idC) = vec[2];
        }
        int st = -1, ed = -1;///st < ed
        vector<int> szC(n + 3, 0);
        function<void(int, int)> dfs = [&] (int u, int p) {
            szC[u] = 1;
            iter (&v, ke[u]) {
                if (v == p) continue;
                dfs(v, u);
                pii c1 = {u, n - szC[v]}, c2 = {v, szC[v]};
                if (c1.se > c2.se) swap(c1, c2);
                if (c1.se >= A && c2.se >= B) {
                    st = c1.fs;
                    ed = c2.fs;
                }
                szC[u] += szC[v];
            }
        };
        dfs(1, 0);
        if (st == -1) {
//            rep (i, 1, n) cout << 0 <<" ";
            return vector<int> (n, 0);
        }
        vector<int> Ans(n + 3, idC);
        vector<int> szCol(4, 0);
        szCol[idA] = A;
        szCol[idB] = B;
        function<void(int, int, int)> color = [&] (int u, int p, int col){
            if (szCol[col] > 0)
                Ans[u] = col;
            --szCol[col];
            iter (&v, ke[u]) {
                if (v != p) color (v, u, col);
            }
        };
        color (st, ed, idA);
        color (ed, st, idB);
//        rep (i, 1, n) cout << Ans[i] <<" ";
        vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
        return subAns;
    }
}

namespace sub4 {

    struct Disjoint_set {
        int lab[N], sz[N];

        void init (int n) {
            rep (i, 1, n) lab[i] = i, sz[i] = 1;
        }
        int Find (int u) {
            return u == lab[u] ? u : lab[u] = Find(lab[u]);
        }
        void Join (int u, int v) {
            u = Find(u);
            v = Find(v);
            if (v == u) return;
            if (sz[u] < sz[v]) swap(u, v);
            sz[u] += sz[v];
            lab[v] = u;
        }
    }DSU;

    vector<int> solution()  {
        int idA, idB, idC; { ///màu gốc của màu A
            vector<pii> vec = { MP(A, 1), MP(B, 2), MP(C, 3) };
            sort (ALL(vec));
            tie(A, idA) = vec[0], tie(B, idB) = vec[1], tie(C, idC) = vec[2];
        }
        vector<vector<int>> adj(n + 3);
        vector<int> deg(n + 3, 0), dd(n + 3, 0);
        function<void(int)> dfs = [&] (int u) {
            dd[u] = 1;
            iter (&v, ke[u]) {
                if (dd[v]) continue;
                adj[u].pb(v);
                adj[v].pb(u);
                dfs(v);
            }
        };
        dfs(1);
        queue<int> Q;
        rep (u, 1, n) {
            deg[u] = SZ(adj[u]);
            if (deg[u] == 1) {
                Q.push(u);
            }
        }
        vector<int> Ans(n + 3, idA);
        int numA = n;
        int rootB = -1;
        DSU.init(n);
        while (numA > A) {
            int u = Q.front();
            Q.pop();
            --numA;
            Ans[u] = idC;
//            cout << u <<"\n";
            deg[u] = -1;
            iter (&v, adj[u]) {
                if (deg[v] != -1) {
                    --deg[v];
                    if (deg[v] == 1) Q.push(v);
                }
            }
            iter (&v, ke[u]) {
                if (deg[v] == -1) {
                    DSU.Join(u, v);
                }
            }
            int curRoot = DSU.Find(u);
            if (DSU.sz[curRoot] >= B) {
                rootB = curRoot;
            }
        }
        if (rootB == -1) {
            return vector<int> (n, 0);
        }
        int szB = B;
        dd.assign(n + 3, 0);
        function<void(int)> coloring = [&] (int u) {
            if (szB > 0) Ans[u] = idB;
            --szB;
            dd[u] = 1;
            iter (&v, ke[u]) {
                if (deg[v] != -1 || dd[v]) continue;
                coloring(v);
            }
        };
        coloring(rootB);
//        rep (i, 1, n) cout << Ans[i] <<" ";
        vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
        return subAns;
    }

}

vector<int> find_split (int _n, int _A, int _B, int _C, vector<int> _u, vector<int> _v) {
    n = _n;
    m = SZ(_u);
    A = _A;
    B = _B;
    C = _C;
    rep (i, 1, m) {
        int u = _u[i - 1], v = _v[i - 1];
        ++u, ++v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    if (sub1 :: check()) return sub1 :: solution();
    else if (sub2 :: check()) return sub2 :: solution();
    else if (sub3 :: check()) return sub3 :: solution();
    else return sub4 :: solution();
}

void solution () {
    vector<int> cur = find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5}, {1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
    iter (&id, cur) cout << id <<" ";
    cout<<"\n";

//    cin >> n >> m >> A >> B >> C;
//    rep (i, 1, m) {
//        int u, v;
//        cin >> u >> v;
//        ke[u].pb(v);
//        ke[v].pb(u);
//    }
//    if (sub1 :: check()) sub1 :: solution();
//    else if (sub2 :: check()) sub2 :: solution();
//    else sub3 :: solution();
}

//#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
//main () {
////    file("DIAMETER");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +21

1 2
2 8
8 4
1 9
1 3
1 7
7 6
6 5
cận trên để giảm không gian và thời gian của mô hình bài toán
cận dưới để có thêm insight về kết quả bài toán

gọi sao cho có lợi cho mình nhất
*/

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