Submission #1246084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246084		qwusha	Split the Attractions (IOI19_split)	C++20	18 / 100	346 ms	37124 KiB

split

#include "split.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second
typedef long long ll;
using namespace std;

int inf = 1e9 + 7;

vector<vector<pair<int, int>>> g;


vector<int> used;
vector<int> active;
int cnt;
int B;

void dfs(int v) {
    if (cnt == B)
        return;
    used[v] = 1;
    cnt++;
    for (auto [u, w] : g[v]) {
        if (!active[w])
            continue;
        if (!used[u]) {
            dfs(u);
        }
    }
}

vector<int> sz;
vector<int> par;

void dfs_sz(int v, int p = -1) {
    par[v] = p;
    sz[v] = 1;
    for (auto [u, w]: g[v]) {
        if (!used[u]) {
            dfs_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

int centr = 0;
void find_cen(int v, int n) {
    bool ok = 1;
    for (auto [u, w] : g[v]) {
        if (sz[u] > n / 2) {
            ok = 0;
            find_cen(u, n);
        }
    }
    if (ok)
        centr = v;
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    g.assign(n, {});
    int m = p.size();
    active.assign(m, 1);
    map<pair<int, int>, int> edg;
    for (int i = 0; i < m; i++) {
        g[p[i]].push_back({q[i], i});
        g[q[i]].push_back({p[i], i});
        edg[{p[i], q[i]}] = i;
        edg[{q[i], p[i]}] = i;
    }

    bool two = 1;
    int mini = inf, indmi = -1;
    for (int i = 0; i < n; i++) {
        if (g[i].size() > 2)
            two = 0;
        if (g[i].size() < mini) {
            mini = g[i].size();
            indmi = i;
        }
    }
    if (two) {
        vector<int> res(n, 3);
        res[indmi] = 1;
        int last = indmi;
        int cur = g[indmi][0].fi;
        for (int i = 0; i < a - 1; i++) {
            res[cur] = 1;
            int tr = cur;
            cur = g[cur][0].fi + g[cur][1].fi - last;
            last = tr;
        }
        for (int i = 0; i < b; i++) {
            res[cur] = 2;
            int tr = cur;
            cur = g[cur][0].fi + g[cur][1].fi - last;
            last = tr;
        }
        return res;
    } else if (a == 1) {
        used.assign(n, 0);
        cnt = 0;
        B= b;
        dfs(0);
        vector<int> res(n, 3);
        for (int i = 0; i < n; i ++) {
            if (used[i])
                res[i] = 2;
        }
        for (int i = 0; i < n; i++) {
            if (res[i] == 3) {
                res[i] = 1;
                break;
            }
        }
        return res;
    } else {
        used.assign(n, 0);
        sz.assign(n, 0);
        dfs_sz(0);
        used.assign(n, 0);
        par.assign(n, 0);
        centr = 0;
        find_cen(0, n);
        int cent = centr;
        if (a > b) swap(a, b);
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);
        int maxi = n - sz[cent];
        int neig = par[cent];
        for (auto [u,w] : g[cent]) {
            if (u != par[cent]) {
                if (maxi < sz[u]) {
                    maxi = sz[u];
                    neig = u;
                }
            }
        }
        vector<int> res(n, 0);
        if (maxi < a) {
            return res;
        }
        for (int i = 0; i < n; i++) 
            res[i] = 3;
        active[edg[{cent, neig}]] = 0;
        B = a;
        cnt = 0;
        used.assign(n, 0);
        dfs(neig);
        for (int i = 0; i < n; i++) {
            if (used[i])
                res[i] = 1;
        }
        B = b;
        cnt = 0;
        used.assign(n, 0);
        dfs(cent);
        for (int i = 0; i < n; i++) {
            if (used[i])
                res[i] = 2;
        }
        return res;
    }

}


/*
signed main() {
    int n;
    cin >> n;
    vector<int> s(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> s[i];
    }
    int res = count_swaps(s);
    cout << res << endl;
}
*/

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