Submission #1108289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108289		underwaterkillerwhale	Split the Attractions (IOI19_split)	C++17	Compilation error	0 ms	0 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 = 2e5 + 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<int> candidates; {
            rep (i, 1, n) candidates.pb(i);
            random_shuffle(ALL(candidates));
            candidates.resize(min(n, 100));
        }
        vector<int> Ans;
        bool ok = 0;
        auto process = [&] (int curR) {
            vector<vector<int>> adj(n + 3);
            vector<int> deg(n + 3, 0), dd(n + 3, 0);
            function<void(int)> dfs = [&] (int u) -> pair<bool, vector<int>> {
                dd[u] = 1;
                random_shuffle(ALL(ke[u]));
                iter (&v, ke[u]) {
                    if (dd[v]) continue;
                    adj[u].pb(v);
                    adj[v].pb(u);
                    dfs(v);
                }
            };
            dfs(curR);
            queue<int> Q;
            rep (u, 1, n) {
                deg[u] = SZ(adj[u]);
                if (deg[u] == 1) {
                    Q.push(u);
                }
            }
            int numA = n;
            int rootB = -1;
            vector<int> res(n + 3, idA);
            DSU.init(n);
            while (numA > A) {
                int u = Q.front();
                Q.pop();
                --numA;
                res[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 MP(0, vector<int> ());
            int szB = B;
            dd.assign(n + 3, 0);
            function<void(int)> coloring = [&] (int u) {
                if (szB > 0) res[u] = idB;
                --szB;
                dd[u] = 1;
                iter (&v, ke[u]) {
                    if (deg[v] != -1 || dd[v]) continue;
                    coloring(v);
                }
            };
            coloring(rootB);
            return MP(1, res);
        };
        rep (step, 0, SZ(candidates) - 1) {
            tie(ok, Ans) = process(candidates[step]);
            if (ok) break;
        }
//        rep (i, 1, n) cout << Ans[i] <<" ";
        if (!ok)
            return vector<int> (n, 0);
        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
*/

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:198:13: warning: no return statement in function returning non-void [-Wreturn-type]
  198 |             };
      |             ^
split.cpp: At global scope:
split.cpp:299:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  299 | main () {
      | ^~~~
/usr/bin/ld: /tmp/ccJhp1Jj.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2iASTm.o:split.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status