Submission #1177891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177891		Boycl07	Split the Attractions (IOI19_split)	C++20	100 / 100	75 ms	30536 KiB

split

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

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res > val) return 0; res = val; return 1;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 2e5 + 3;
const int LOG = 20;
const int LIM = 1e6 + 3;

int n, m;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
vector<int> g[N];
vector<int> tree[N];
int sz[N];
int num[N], low[N];
int vis[N];
int cut[N];
int timedfs = 0;

void dfs(int u, int p)
{
    num[u] = low[u] = ++timedfs;
    sz[u] = 1;
    for(int v : g[u])
    {
        if(v != p)
        if(!num[v])
        {
            dfs(v, u);
            minimize(low[u], low[v]);
            tree[u].pb(v);
            sz[u] += sz[v];
        }
        else minimize(low[u], num[v]);
    }

}
vector<pii> C;

int get_centroid(int u)
{
    for(int v : tree[u]) if(sz[v] >= C[0].fi) return get_centroid(v);
    return u;
}

vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q)
{
    n = n_;
    m = sz(p);
    for(int i = 0; i < m; ++i)
    {
        int u = p[i], v = q[i];
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(0, 0);
    C.pb({a, 1});
    C.pb({b, 2});
    C.pb({c, 3});
    sort(all(C));
    vector<int> res(n, C[2].se);
    function<void(int)> color_1 = [&](int u)
    {
        if(C[1].fi) res[u] = C[1].se, --C[1].fi;
        vis[u] = 1;
        for(int v : tree[u]) color_1(v);
    };
    function<void(int)> color_0 = [&](int u)
    {
        if(C[0].fi) res[u] = C[0].se, --C[0].fi;
        vis[u] = 1;
        for(int v : g[u]) if(!vis[v]) color_0(v);
    };
    int cur = get_centroid(0);
    for(int v : tree[cur]) if(low[v] < num[cur] && sz[cur] - sz[v] >= C[0].fi)
    {
        sz[cur] -= sz[v];
        cut[v] = 1;
    }
    if(n - sz[cur] >= C[1].fi) swap(C[0], C[1]);
    if(n - sz[cur] >= C[0].fi)
    {
        --C[1].fi;
        vis[cur] = 1;
        res[cur] = C[1].se;
        for(int v : tree[cur]) if(!cut[v]) color_1(v);
        for(int i = 0; i < n; ++i) if(!vis[i])
        {
            color_0(i);
            break;
        }

    } else return vector<int>(n, 0);
    return res;
}

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