Submission #787218

#	Time	Username	Problem	Language	Result	Execution time	Memory
787218		resting	Split the Attractions (IOI19_split)	C++17	40 / 100	66 ms	27444 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> ss, sz, pp, tin, low, st, res; int curt = 1;
vector<vector<int>> scc, adj;

void dfs(int v, int p) {
    sz[v] = 1;
    low[v] = tin[v] = curt++; pp[v] = p;
    st.push_back(v);
    for (auto& x : adj[v]) {
        if (tin[x]) low[v] = min(low[v], tin[x]);
        else {
            dfs(x, v); sz[v] += sz[x];
            if (low[x] == tin[v]) {
                scc.push_back({});
                while (st.back() != v) { scc.back().push_back(st.back()); st.pop_back(); }
                scc.back().push_back(v);
            }
            low[v] = min(low[v], low[x]);
        }
    }
}

int dfs_fill(int v, int t, int amt) {
    if (!amt || res[v]) return amt;
    res[v] = t; amt--;
    for (auto& x : adj[v]) amt = dfs_fill(x, t, amt);
    return amt;
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int na = 1, nb = 2, nc = 3;
    if (a > b) {
        swap(a, b); swap(na, nb);
    }
    if (b > c) {
        swap(b, c); swap(nb, nc);
    }
    if (a > b) {
        swap(a, b); swap(na, nb);//haha o(n) sorting OwO
    }

    sz = pp = tin = low = ss = res = vector<int>(n, 0);
    adj.assign(n, {});
    scc.clear();


    int m = p.size();
    for (int i = 0; i < m; i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }

    dfs(0, 0);

    int mxi = -1;
    assert(scc.size());
    for (int i = 0; i < scc.size(); i++) {
        {
            int mxsz = 0;
            for (auto& x : scc[i]) {
                mxsz = max(mxsz, sz[x]);
                ss[x] = sz[x];
            }
            for (auto& x : scc[i]) {
                if (x) ss[pp[x]] -= sz[x];
                if (sz[x] == mxsz) ss[x] += n - sz[x];
            }
            int sm = 0;
            for (auto& x : scc[i]) sm += ss[x];
            assert(sm == n);
            for (auto& x : scc[i]) {
                if (ss[x] >= b) {
                    if (n - ss[x] >= a) {
                        mxi = i;
                    }
                    goto end;
                }
            }
            mxi = i; break;
        }
    end:;
    }
    if (mxi == -1) return res;


    {
        vector<int> mark1(n, 0);
        vector<int> mark2(n, 0);
        vector<int> mark3(n, 0);
        vector<int> cntc(n, 0);

        int mxsz = 0;
        for (auto& x : scc[mxi]) {
            mark1[x] = 1;
            mxsz = max(mxsz, sz[x]);
            ss[x] = sz[x];
            res[x] = -1;
        }
        for (auto& x : scc[mxi]) {
            if (x) { ss[pp[x]] -= sz[x]; cntc[pp[x]]++; }
            if (sz[x] == mxsz) ss[x] += n - sz[x];
        }
        for (auto& x : scc[mxi]) {
            if (ss[x] >= b) {
                res[x] = nb; b--;
                for (auto& x : adj[x])
                    if (!mark1[x])
                        b = dfs_fill(x, nb, b);
                assert(!b);
                for (auto& x : scc[mxi]) {
                    if (res[x] == -1) res[x] = 0;
                }
                for (auto& x : scc[mxi]) {
                    if (!res[x]) {
                        a = dfs_fill(x, na, a);
                    }
                }
                assert(!a);
                //assert(!a);
                goto end2;
            }
        }

        vector<int> st;
        for (auto& x : scc[mxi]) if (cntc[x] == 0) st.push_back(x);
        while (st.size()) {
            int c = st.back(); st.pop_back();
            mark2[c]++;
            ss[pp[c]] += ss[c];
            cntc[pp[c]]--;
            if (!cntc[pp[c]]) st.push_back(pp[c]);
            c = pp[c];
            if (ss[c] >= b) {
                assert(ss[c] < 2 * b);
                vector<int> q; q.push_back(c);
                while (q.size()) {
                    int t = q.back(); q.pop_back();
                    mark3[t] = 1;mark2[t] = 0;
                    res[t] = 0;
                    if (b) {
                        res[t] = nb; b--;
                    }
                    for (auto& x : adj[t]) {
                        if (!mark1[x])
                            b = dfs_fill(x, nb, b);
                        if (mark2[x]) q.push_back(x);
                    }
                }
                assert(!b);

                for (auto& x : scc[mxi]) {
                    if (res[x] == -1) res[x] = 0;
                }
                for (auto& x : scc[mxi])
                    if (!mark3[x]) {
                        a = dfs_fill(x, na, a);
                    }
                goto end2;
            }
        }
    }


end2:;
    for (auto& x : res)if (!x)x = nc;
    return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < scc.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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