Submission #645215

#	Time	Username	Problem	Language	Result	Execution time	Memory
645215		LeonaRaging	Split the Attractions (IOI19_split)	C++14	18 / 100	122 ms	24936 KiB

split

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;

int n, m, node[maxn];
int tin[maxn], tout[maxn], low[maxn], sz[maxn], res[maxn];
vector<int> adj[maxn], g[maxn], cut;
pair<int,int> req[4];
bool ok = false;

void dfs1(int u, int p) {
    // clog << u << ' ' << p << '\n';
    tin[u] = low[u] = ++tin[0];
    node[tin[0]] = u;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (!tin[v]) {
            dfs1(v, u);
            sz[u] += sz[v];
            g[u].pb(v);
            g[v].pb(u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }
    tout[u] = tin[0];
}

void dfs2(int u, int p) {
    if (ok) return;
    bool flag = true;
    for (int v : g[u])
        if (v != p) {
            dfs2(v, u);
            if (sz[v] >= req[1].fi) 
                flag = false;
        }
    if (flag && sz[u] >= req[1].fi) {
        int rem = n - sz[u];
        if (rem < req[1].fi) {
            vector<int>().swap(cut);
            for (int v : g[u])
                if (low[v] < tin[u] && rem > req[1].fi) {
                    rem -= sz[v];
                    cut.pb(v);
                }
        }
        if (rem >= req[1].fi) {
            for (auto v : cut) {
                for (int i = tin[v]; i <= tout[v]; i++)
                    res[node[i]] = 3;
            }
            int cnt = 0, col = 1;
            for (int i = tin[u]; i <= tout[u]; i++)
                if (!res[node[i]]) {
                    res[node[i]] = col;
                    cnt++;
                    if (cnt == req[1].fi && col == 1)
                        col = 3;
                }
            cnt = 0, col = 2;
            for (int i = 1; i < tin[u]; i++) {
                res[node[i]] = col;
                cnt++;
                if (cnt == req[2].fi && col == 2)
                    col = 3;
            }
            for (int i = tout[u] + 1; i <= n; i++) {
                res[node[i]] = col;
                cnt++;
                if (cnt == req[2].fi && col == 2)
                    col = 3;
            }
            ok = true;
        }
    }
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
    n = _n, m = p.size();
    req[1] = {a, 1}; req[2] = {b, 2}; req[3] = {c, 3};
    sort(req + 1, req + 4);
    for (int i = 0; i < m; i++) {
        int u = p[i], v = q[i];
        u++, v++;        
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = req[res[i + 1]].se;
    return ans;
}

// int main()
// {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     //freopen(".INP", "r", stdin);
//     //freopen(".OUT", "w", stdout);
//     int n, m, a, b, c;
//     vector<int> p, q;
//     cin >> n >> m >> a >> b >> c;
//     for (int i = 1; i <= m; i++) {
//         int u, v; cin >> u >> v;
//         p.pb(u); q.pb(v);
//     }
//     vector<int> ans = find_split(n, a, b, c, p, q);
//     for (auto i : ans)
//         cout << i << ' ';
// }

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