제출 #1055070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055070		RecursiveCo	Split the Attractions (IOI19_split)	C++17	40 / 100	47 ms	13172 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);
    
    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);
    }

    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;
    
    for (int r = 0; r < (n >= 3000? 1: n); r++) {
        visited.clear();
        visited.resize(n, false);
        sz.clear();
        sz.resize(n, 1);
        dfs(r);

        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 {
            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) continue;
        for (int i = 0; i < n; i++) visited[i] = false;
        assign(r, 0);
        return ans;
    }
    return ans;
}

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