oj.uz

답안 #941435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941435 2024-03-09T00:13:13 Z Programmer123 Split the Attractions (IOI19_split) C++17
18 / 100
 57 ms 12368 KB 
#include "split.h"
#include <bits/stdc++.h>

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
    std::vector<int> res(n);
    std::vector<int> connections[n];
    for (int i = 0; i < p.size(); ++i) {
        connections[p[i]].push_back(q[i]);
        connections[q[i]].push_back(p[i]);
    }
    bool s1 = true;
    for (int i = 0; i < n; ++i) {
        if (connections[i].size() > 2) s1 = false;
    }
    if (s1) {
        int start = 0;
        for (int i = 0; i < n; ++i) {
            if (connections[i].size() == 1) {
                start = i;
                break;
            }
        }
        std::vector<int> order;
        while (order.size() < n) {
            order.push_back(start);
            int next = connections[start][0];
            if (connections[next].size() == 2 && connections[next][0] == start) {
                std::swap(connections[next][0], connections[next][1]);
            }
            start = next;
        }
        for (int i = 0; i < a; ++i) {
            res[order[i]] = 1;
        }
        for (int i = a; i < a + b; ++i) {
            res[order[i]] = 2;
        }
        for (int i = a + b; i < n; ++i) {
            res[order[i]] = 3;
        }
    } else if (a == 1) {
        std::queue<int> bfs;
        bfs.push(0);
        res[0] = 2;
        int rem = b - 1;
        while (!bfs.empty()) {
            auto next = bfs.front();
            bfs.pop();
            for (auto x: connections[next]) {
                if (!rem) break;
                if (res[x]) continue;
                res[x] = 2;
                bfs.push(x);
                rem--;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (res[i] == 0) {
                res[i] = 1;
                break;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (res[i] == 0) res[i] = 3;
        }
    } else if (p.size() == n - 1) {
        int size[n];
        int parent[n];
        std::function<int(int, int)> dfs = [&](int node, int from) {
            parent[node] = from;
            int res = 1;
            for (auto x: connections[node]) {
                if (x == from) continue;
                res += dfs(x, node);
            }
            return size[node] = res;
        };
        dfs(0, 0);
        std::function<int(int, int, int)> fill = [&](int node, int num, int type) {
            if (num == 0) return 0;
            num--;
            res[node] = type;
            for (auto x: connections[node]) {
                if (x == parent[node]) continue;
                num = fill(x, num, type);
            }
            return num;
        };
        std::function<void(int, int, int)> expand = [&](int node, int num, int type) {
            std::queue<int> bfs;
            bfs.push(node);
            res[node] = type;
            int rem = num - 1;
            while (!bfs.empty()) {
                auto next = bfs.front();
                bfs.pop();
                for (auto x: connections[next]) {
                    if (!rem) break;
                    if (res[x]) continue;
                    res[x] = num;
                    bfs.push(x);
                    rem--;
                }
            }
        };
        std::function<void(int)> fix = [&](int type) {
            for (int i = 0; i < n; ++i) {
                if (res[i] == 0) res[i] = type;
            }
        };
        for (int i = 0; i < n; ++i) {
            int s = size[i];
            int so = n - size[i];
            if (s >= a) {
                if (so >= b) {
                    fill(i, a, 1);
                    expand(parent[i], b, 2);
                    fix(3);
                    return res;
                }
                if (so > c) {
                    fill(i, a, 1);
                    expand(parent[i], c, 3);
                    fix(2);
                    return res;
                }
            }
            if (s >= b) {
                if (so >= a) {
                    fill(i, b, 2);
                    expand(parent[i], a, 1);
                    fix(3);
                    return res;
                }
                if (so > c) {
                    fill(i, b, 2);
                    expand(parent[i], c, 3);
                    fix(1);
                    return res;
                }
            }
            if (s >= c) {
                if (so >= b) {
                    fill(i, c, 3);
                    expand(parent[i], b, 2);
                    fix(1);
                    return res;
                }
                if (so > a) {
                    fill(i, c, 3);
                    expand(parent[i], a, 1);
                    fix(2);
                    return res;
                }
            }
        }
    }
    return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < p.size(); ++i) {
      |                     ~~^~~~~~~~~~
split.cpp:24:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |         while (order.size() < n) {
      |                ~~~~~~~~~~~~~^~~
split.cpp:66:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     } else if (p.size() == n - 1) {
      |                ~~~~~~~~~^~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 40 ms 9680 KB ok, correct split
8 Correct 40 ms 9696 KB ok, correct split
9 Correct 39 ms 9664 KB ok, correct split
10 Correct 40 ms 9664 KB ok, correct split
11 Correct 54 ms 9592 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB ok, correct split
2 Correct 0 ms 432 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 47 ms 10580 KB ok, correct split
5 Correct 38 ms 9052 KB ok, correct split
6 Correct 39 ms 9432 KB ok, correct split
7 Correct 41 ms 9428 KB ok, correct split
8 Correct 57 ms 12368 KB ok, correct split
9 Correct 40 ms 9020 KB ok, correct split
10 Correct 34 ms 9172 KB ok, correct split
11 Correct 33 ms 9172 KB ok, correct split
12 Correct 36 ms 9684 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB invalid split: #1=1, #2=2, #3=2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 40 ms 9680 KB ok, correct split
8 Correct 40 ms 9696 KB ok, correct split
9 Correct 39 ms 9664 KB ok, correct split
10 Correct 40 ms 9664 KB ok, correct split
11 Correct 54 ms 9592 KB ok, correct split
12 Correct 1 ms 600 KB ok, correct split
13 Correct 0 ms 432 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 47 ms 10580 KB ok, correct split
16 Correct 38 ms 9052 KB ok, correct split
17 Correct 39 ms 9432 KB ok, correct split
18 Correct 41 ms 9428 KB ok, correct split
19 Correct 57 ms 12368 KB ok, correct split
20 Correct 40 ms 9020 KB ok, correct split
21 Correct 34 ms 9172 KB ok, correct split
22 Correct 33 ms 9172 KB ok, correct split
23 Correct 36 ms 9684 KB ok, correct split
24 Incorrect 0 ms 344 KB invalid split: #1=1, #2=2, #3=2
25 Halted 0 ms 0 KB -