Submission #1165360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165360		browntoad	Split the Attractions (IOI19_split)	C++20	100 / 100	73 ms	27336 KiB

split

#include <bits/stdc++.h>
#include "split.h"
// #include "grader.cpp" // rem
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 1e5+5;
const ll inf = 1e9;
const ll mod = 998244353;

ll pw(ll x, ll p, ll m){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= x;
            ret %= m;
        }
        x *= x;
        x %= m;
        p >>= 1;
    }
    return ret;
}
ll inv(ll x, ll m){
    return pw(x, m-2, m);
}

int n, a, b, c; // a, b, c sorted in this case
vector<int> g[maxn];

vector<int> sz(maxn), low(maxn), occ(maxn), dep(maxn);

bool dfsocc = 0;

vector<int> S1, S2;
vector<bool> s1occ(maxn), s2occ(maxn);

void dfs2(int x, int prev){
    S1.pb(x);
    s1occ[x] = 1;
    for (auto y:g[x]){
        if (dep[y] == dep[x]+1){
            dfs2(y, x);
        }
    }
}
void dfs3(int x, int prev){
    S2.pb(x);
    s2occ[x] = 1;
    for (auto y:g[x]){
        if (dep[y] == dep[x]+1){
            dfs3(y, x);
        }
    }
}
void dfs4(int x){ // so that prefixes can be connected in S1
    s1occ[x] = 1;
    S1.pb(x);
    for (auto y:g[x]){
        if (s1occ[y] || s2occ[y]) continue;
        dfs4(y);
    }
}
void dfs1(int x, int prev){
    occ[x] = 1;
    sz[x] = 1;
    low[x] = dep[x];
    for (auto y:g[x]){
        if (y == prev) continue;
        if (occ[y]){
            low[x] = min(low[x], low[y]);
        }
        else{
            dep[y] = dep[x]+1;
            dfs1(y, x);
            low[x] = min(low[x], low[y]);
            sz[x] += sz[y];
        }
    }

    if (sz[x] >= a && !dfsocc){
        dfsocc = 1;

        dfs2(x, prev); // get all the s1occ
        S1.clear();
        REP(i, n){
            s1occ[i] = (s1occ[i]^1);
            if (s1occ[i]) S1.pb(i);
        }

        for (auto y:g[x]){
            if (SZ(S1) >= a) break;
            if (dep[y] == dep[x]+1 && low[y] < dep[x]){
                dfs2(y, x);
            }
        }

        S2.pb(x);
        s2occ[x] = 1;
        for (auto y:g[x]){
            if (dep[y] == dep[x]+1 && !s1occ[y]){
                dfs3(y, x);
            }
        }

        if (SZ(S1)){
            int u = S1[0]; S1.clear();
            fill(ALL(s1occ), 0);
            dfs4(u);
        }
        
        return;
    }
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	n = N;
	dfsocc = 0;
	vector<pii> pus = {{A, 0}, {B, 1}, {C, 2}};
	REP(i, SZ(p)){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
	}
	sort(ALL(pus)); // by smallest
	a = pus[0].f, b = pus[1].f;
    dfs1(0, -1);

    vector<int> ret;
    REP(i, n) ret.pb(-1);
    if (SZ(S1) > SZ(S2)) swap(S1, S2);
    if (SZ(S1) < a){
        fill(ALL(ret), 0);
        return ret;
    }

    // match S1 with a, S2 with b
    REP(i, a) ret[S1[i]] = 0;
    REP(i, b) ret[S2[i]] = 1;
    REP(i, n) if (ret[i] == -1) ret[i] = 2;

	REP(i, n) ret[i] = pus[ret[i]].s + 1; // convert it back
	return ret;
}
/*
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6

5 6
2 2 1
0 2
0 1
1 2
1 3
2 3
3 4
*/

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