oj.uz

답안 #718333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718333 2023-04-03T21:29:38 Z bebra Split the Attractions (IOI19_split) C++17
22 / 100
 465 ms 1048576 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
vector<int> g[MAX_N];
int color[MAX_N];
bool block[MAX_N];
int sz[MAX_N];

int n;
int val[3];
int order[3];

void dfs_color(int v, int p, int c, int& cnt) {
    if (cnt == 0) return;
    --cnt;
    color[v] = c;
    for (auto u : g[v]) {
        if (u == p || block[u]) continue;
        dfs_color(u, v, c, cnt);
    }
}

bool dfs_calc(int v = 0, int p = -1) {
    sz[v] = 1;
    for (auto u : g[v]) {
        if (u == p) continue;
        if (dfs_calc(u, v)) return true;
        sz[v] += sz[u];
    }

    for (int t = 0; t <= 1; ++t) {
        if (sz[v] >= val[order[t]] && n - sz[v] >= val[order[t ^ 1]]) {
            block[v] = true;
            int curr_cnt1 = val[order[t]];
            int curr_cnt2 = val[order[t ^ 1]];
            dfs_color(v, p, order[t], curr_cnt1);
            dfs_color(0, -1, order[t ^ 1], curr_cnt2);
            return true;
        }
    }

    return false;
}


vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
    n = _n;
    int m = p.size();

    for (int i = 0; i < m; ++i) {
        int u = p[i];
        int v = q[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    val[0] = a;
    val[1] = b;
    val[2] = c;

    iota(order, order + 3, 0);
    sort(order, order + 3, [&](int lhs, int rhs) {
        return order[lhs] < order[rhs];
    });

    fill_n(color, n, order[2]);
    vector<int> res(n);
    if (!dfs_calc()) {
        return res;
    }

    for (int i = 0; i < n; ++i) {
        res[i] = color[i] + 1;
    }

	return res;
}


// int main() {

//     int m;
//     cin >> n >> m;

//     int a, b, c;
//     cin >> a >> b >> c;

//     vector<int> p(m), q(m);
//     for (int i = 0; i < m; ++i) {
//         cin >> p[i] >> q[i];
//     }

//     for (auto x : find_split(n, a, b, c, p, q)) {
//         cout << x << ' ';
//     }
//     cout << '\n';

// }

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB ok, correct split
2 Runtime error 465 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2676 KB ok, correct split
2 Runtime error 452 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB ok, correct split
2 Correct 58 ms 8568 KB ok, correct split
3 Correct 18 ms 4948 KB ok, correct split
4 Correct 1 ms 2644 KB ok, correct split
5 Correct 56 ms 11724 KB ok, correct split
6 Correct 60 ms 11340 KB ok, correct split
7 Correct 75 ms 11208 KB ok, correct split
8 Correct 72 ms 12748 KB ok, correct split
9 Correct 79 ms 10888 KB ok, correct split
10 Correct 17 ms 4668 KB ok, no valid answer
11 Correct 23 ms 5748 KB ok, no valid answer
12 Correct 56 ms 9012 KB ok, no valid answer
13 Correct 51 ms 8804 KB ok, no valid answer
14 Correct 40 ms 9068 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 436 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB ok, correct split
2 Runtime error 465 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -