Submission #724300

#	Time	Username	Problem	Language	Result	Execution time	Memory
724300		PixelCat	Split the Attractions (IOI19_split)	C++14	22 / 100	80 ms	11716 KiB

split

#include "split.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

vector<int> adj[MAXN];
int siz[MAXN];
int vis[MAXN];

int dfs_siz(int n, int p) {
    siz[n] = 1;
    for(auto &i:adj[n]) if(i != p) {
        siz[n] += dfs_siz(i, n);
    }
    return siz[n];
}

vector<int> comp(int n, int ban, int cnt) {
    memset(vis, 0, sizeof(vis));
    vis[ban] = 1; vis[n] = 1;
    queue<int> que;
    que.emplace(n);
    vector<int> res;
    while(!que.empty()) {
        int cur = que.front(); que.pop();
        res.eb(cur);
        cnt--;
        if(cnt == 0) return res;
        for(auto &i:adj[cur]) if(!vis[i]) {
            vis[i] = 1;
            que.emplace(i);
        }
    }
    assert(false);
    return res;
}

vector<int32_t> find_split(int32_t n, int32_t a, int32_t b, int32_t c, vector<int32_t> p, vector<int32_t> q) {
    int x, y;
    {
        vector<int> ord = {a, b, c};
        sort(all(ord));
        x = ord[0]; y = ord[1];
    }
    auto get_id = [&](int k) {
        if(k == a) return 1;
        if(k == b) return 2;
        return 3;
    };

    int m = sz(p);
    assert(m == n - 1);
    For(i, 0, m - 1) {
        int s = p[i];
        int t = q[i];
        adj[s].eb(t);
        adj[t].eb(s);
    }
    dfs_siz(0, -1);
    For(eid, 0, m - 1) {
        int s = p[eid];
        int t = q[eid];
        if(siz[s] < siz[t]) swap(s, t);
        // s is parent
        int s1 = siz[t];
        int s2 = n - s1;
        if(s1 > s2) {
            swap(s1, s2);
            swap(s, t);
        }
        // size of t's side is smaller (s1)
        if(s1 >= x && s2 >= y) {
            // cout << s << " " << t << "\n";
            int i1 = get_id(x);
            vector<int> v1 = comp(t, s, x);
            int i2 = get_id(y);
            vector<int> v2 = comp(s, t, y);
            int i3 = 6 - i1 - i2;

            vector<int> res(n, i3);
            for(auto &i:v1) res[i] = i1;
            for(auto &i:v2) res[i] = i2;
            return res;
        }
    }
    return vector<int>(n, 0);
}

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