제출 #1054966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054966		RecursiveCo	Split the Attractions (IOI19_split)	C++17	18 / 100	49 ms	13144 KiB

split

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adjList;
vector<bool> visited;
vector<int> sz;
vector<int> ans;
vector<pair<int, int>> values;

int threshold1 = 1e9;
int threshold2 = 1e9;
int node = -1;
int insubtree = -1;

void dfs(int v) {
    visited[v] = true;
    for (int con: adjList[v]) {
        if (!visited[con]) {
            dfs(con);
            sz[v] += sz[con];
        }
    }
}

void assign(int v, int mode) {
    if (mode) {
        if (threshold1) ans[v] = values[insubtree].second, threshold1--;
        else ans[v] = values[2].second;
    } else {
        if (threshold2) ans[v] = values[1 - insubtree].second, threshold2--;
        else ans[v] = values[2].second;
    }
    visited[v] = true;
    for (int con: adjList[v]) {
        if (!visited[con]) {
            assign(con, con == node? 1: mode);
        }
    }
}

vector<int> find_split(int n, int x, int y, int z, vector<int> u, vector<int> v) {
    int m = u.size(); // = v.size()
    adjList.clear();
    adjList.resize(n);
    visited.clear();
    visited.resize(n, false);
    sz.clear();
    sz.resize(n, 1);
    for (int i = 0; i < m; i++) {
        int a = u[i];
        int b = v[i];
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    dfs(0);

    ans.clear();
    ans.resize(n, 0);

    values.push_back({x, 1});
    values.push_back({y, 2});
    values.push_back({z, 3});
    sort(values.begin(), values.end());
    int a = values[0].first;
    int b = values[1].first;
    int abovea = 1e9;
    int mini1 = -1;
    for (int i = 0; i < n; i++) if (sz[i] >= a && sz[i] < abovea) abovea = sz[i], mini1 = i;
    if (n - abovea >= b) {
        threshold1 = a;
        threshold2 = b;
        node = mini1;
        insubtree = 0;
    } else {
        return ans;
        int aboveb = 1e9;
        int mini2 = -1;
        for (int i = 0; i < n; i++) if (sz[i] >= b && sz[i] < aboveb) aboveb = sz[i], mini2 = i;
        if (n - aboveb >= a) {
            threshold1 = b;
            threshold2 = a;
            node = mini2;
            insubtree = 1;
        }
    }
    if (threshold1 == 1e9) return ans;
    for (int i = 0; i < n; i++) visited[i] = false;
    assign(0, 0);
    return ans;
}

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