Submission #645242

#	Time	Username	Problem	Language	Result	Execution time	Memory
645242		LeonaRaging	Split the Attractions (IOI19_split)	C++14	100 / 100	187 ms	30244 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, cnt, node[maxn];
int tin[maxn], tout[maxn], low[maxn], sz[maxn], res[maxn];
vector<int> adj[maxn], g[maxn];
map<int,int> bad;
pair<int,int> req[5];
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);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }
    tout[u] = tin[0];
}

void dfs3(int u, int p, int col, vector<int> adj[]) { // to mau
    if (cnt == req[col].fi) return;
    res[u] = col;
    // if (col == 1) clog << u << ' ';
    cnt++;
    for (int v : adj[u])
        if (!bad[v] && v != p && res[v] == 3)
            dfs3(v, u, col, adj);
}

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) {
            bad.clear();
            for (int v : g[u])
                if (low[v] < tin[u] && rem < req[1].fi) {
                    rem += sz[v];
                    bad[v] = 1;
                }
        }
        // clog << u << ' ' << p;
        if (rem >= req[1].fi) {
            for (int i = 1; i <= n; i++)
                res[node[i]] = 3;
            int col1 = 1, col2 = 2;
            if (rem < req[2].fi)
                swap(col1, col2);
            dfs3(u, p, col1, g);
            bad.clear(); cnt = 0;
            dfs3(p, 0, col2, adj);
            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: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36