제출 #1030776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030776		Zicrus	Split the Attractions (IOI19_split)	C++17	29 / 100	81 ms	17748 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;

typedef long long ll;

vector<vector<ll>> adj;
vector<bool> vst;
vector<ll> subSize;
vector<ll> parent;
vector<int> res;

ll dfs(ll node) {
    vst[node] = true;
    ll sum = 1;
    for (auto &e : adj[node]) {
        if (!vst[e]) {
            sum += dfs(e);
        }
        else {
            parent[node] = e;
        }
    }
    subSize[node] = sum;
    return sum;
}

int subG, subGVal;
void dfs2(ll node) {
    
    if (subGVal-- > 0) {
        res[node] = subG;
    }
    else {
        return;
    }
    vst[node] = true;

    for (auto &e : adj[node]) {
        if (e == parent[node]) continue;
        dfs2(e);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size();
    res = vector<int>(n);
    adj = vector<vector<ll>>(n);
    parent = vector<ll>(n);
    subSize = vector<ll>(n);
    for (int i = 0; i < m; i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    vst = vector<bool>(n);
    subSize[0] = dfs(0);

    bool possible = 0;
    ll id = 0;
    ll low = min({a, b, c}), high = n - min({a, b, c});
    for (int i = 0; i < n; i++) {
        if (subSize[i] >= low && subSize[i] <= high) { possible = 1; id = i; }
    }

    if (!possible) {
        return res;
    }

    vst = vector<bool>(n);

    vector<pair<ll, ll>> g;
    g.push_back({a, 1});
    g.push_back({b, 2});
    g.push_back({c, 3});
    sort(g.begin(), g.end());

    subG = subSize[id] < n/2 ? g[0].second : g[1].second;
    subGVal = subSize[id] < n/2 ? g[0].first : g[1].first;
    dfs2(id);
    ll pr = parent[id];
    subG = subSize[id] >= n/2 ? g[0].second : g[1].second;
    subGVal = subSize[id] >= n/2 ? g[0].first : g[1].first;
    dfs(id);
    dfs2(pr);

    for (auto &e : res) {
        if (!e) e = g[2].second;
    }

    return res;
}

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