Submission #1108274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108274		underwaterkillerwhale	Split the Attractions (IOI19_split)	C++17	40 / 100	83 ms	41280 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;
    }

}

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 vector<int> (n, 0);
}

void solution () {
//    vector<int> cur = find_split(9, 3, 4, 2, {1, 2, 0, 0, 0}, {1, 2, 3, 4, 5});
//    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