Submission #1009001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009001		thangdz2k7	Split the Attractions (IOI19_split)	C++17	0 / 100	552 ms	1048576 KiB

split

#include <bits/stdc++.h>
#define ALL(v) (v).begin(), (v).end()
#define pb push_back

using namespace std;

const int N = 1e5 + 5;

vector <pair <int, int>> type(3);
vector <int> adj[N], tree[N];
int st[N], ed[N], cnt = 0, sz[N], r;

int dfs(int u){
    st[u] = ++ cnt;
    sz[u] = 1;

    for (auto v : adj[u]){
        if (!st[v]){
            tree[u].pb(v);
            int k = dfs(v);
            sz[u] += sz[v];
            if (sz[v] >= type[0].first) return k;
        }
    }

    ed[u] = cnt;
    return u;

}

vector <int> ans;
int rc[N];

bool dfs2(int u){
    for (int v : tree[u]) if (dfs2(v)) return true;
    for (int v : adj[u]) if (ed[v] < st[r] || st[v] > ed[r]) return true;
    return false;
}

void ck(int u){
    rc[u] = 1;
    for (int v : tree[u]) ck(v);
}

void ass(int u, pair <int, int> type){
    if (type.first){
        ans[u] = type.second;
        -- type.first;
    }
    for (int v : tree[u]) if (!rc[v]) ass(v, type);
}

void ass1(int u, pair <int, int> type){
    if (type.first){
        ans[u] = type.second;
        -- type.first;
    }
    for (int v : adj[u]) if (!ans[v]) ass1(v, type);
}

vector <int> find_split(int n, int a, int b, int c, vector <int> u, vector <int> v){
    ans.resize(n, 0);
    type[0] = {a, 1}, type[1] = {b, 2}, type[2] = {c, 3};
    sort(ALL(type));
    for (int i = 0; i < u.size(); ++ i) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
    r = dfs(0);
    int p1 = sz[r];
    int p2 = n - sz[r];

    for (int v : tree[r]){
        if (dfs2(v)){
            if (p1 - sz[v] >= type[0].first) {
                p1 -= sz[v];
                p2 += sz[v];
                ck(v);
            }
        }
    }

    if (p2 < a) return ans;
    if (p2 >= b){
        ass(r, type[0]);
        ass1(0, type[1]);
    }
    else {
        ass(r, type[1]);
        ass1(0, type[0]);
    }

    for (int i = 0; i < n; ++ i) if (!ans[i]) ans[i] = type[2].second;

    return ans;
}

Compilation message (stderr)

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

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