oj.uz

Submission #941436

# Submission time Handle Problem Language Result Execution time Memory
941436 2024-03-09T00:15:37 Z Programmer123 Split the Attractions (IOI19_split) C++17
40 / 100
 61 ms 13848 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] = type;
                    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

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 42 ms 8412 KB ok, correct split
8 Correct 50 ms 8504 KB ok, correct split
9 Correct 39 ms 8404 KB ok, correct split
10 Correct 39 ms 8408 KB ok, correct split
11 Correct 49 ms 8408 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 47 ms 8788 KB ok, correct split
5 Correct 37 ms 8024 KB ok, correct split
6 Correct 41 ms 8528 KB ok, correct split
7 Correct 39 ms 8412 KB ok, correct split
8 Correct 61 ms 10264 KB ok, correct split
9 Correct 37 ms 7772 KB ok, correct split
10 Correct 33 ms 8416 KB ok, correct split
11 Correct 42 ms 8400 KB ok, correct split
12 Correct 43 ms 8392 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 42 ms 9820 KB ok, correct split
3 Correct 16 ms 4184 KB ok, correct split
4 Correct 0 ms 344 KB ok, correct split
5 Correct 45 ms 12880 KB ok, correct split
6 Correct 46 ms 12632 KB ok, correct split
7 Correct 56 ms 12344 KB ok, correct split
8 Correct 48 ms 13848 KB ok, correct split
9 Correct 45 ms 12116 KB ok, correct split
10 Correct 16 ms 3380 KB ok, no valid answer
11 Correct 20 ms 4956 KB ok, no valid answer
12 Correct 37 ms 9932 KB ok, no valid answer
13 Correct 40 ms 9780 KB ok, no valid answer
14 Correct 34 ms 10184 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 42 ms 8412 KB ok, correct split
8 Correct 50 ms 8504 KB ok, correct split
9 Correct 39 ms 8404 KB ok, correct split
10 Correct 39 ms 8408 KB ok, correct split
11 Correct 49 ms 8408 KB ok, correct split
12 Correct 0 ms 348 KB ok, correct split
13 Correct 0 ms 348 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 47 ms 8788 KB ok, correct split
16 Correct 37 ms 8024 KB ok, correct split
17 Correct 41 ms 8528 KB ok, correct split
18 Correct 39 ms 8412 KB ok, correct split
19 Correct 61 ms 10264 KB ok, correct split
20 Correct 37 ms 7772 KB ok, correct split
21 Correct 33 ms 8416 KB ok, correct split
22 Correct 42 ms 8400 KB ok, correct split
23 Correct 43 ms 8392 KB ok, correct split
24 Correct 1 ms 348 KB ok, correct split
25 Correct 42 ms 9820 KB ok, correct split
26 Correct 16 ms 4184 KB ok, correct split
27 Correct 0 ms 344 KB ok, correct split
28 Correct 45 ms 12880 KB ok, correct split
29 Correct 46 ms 12632 KB ok, correct split
30 Correct 56 ms 12344 KB ok, correct split
31 Correct 48 ms 13848 KB ok, correct split
32 Correct 45 ms 12116 KB ok, correct split
33 Correct 16 ms 3380 KB ok, no valid answer
34 Correct 20 ms 4956 KB ok, no valid answer
35 Correct 37 ms 9932 KB ok, no valid answer
36 Correct 40 ms 9780 KB ok, no valid answer
37 Correct 34 ms 10184 KB ok, no valid answer
38 Incorrect 0 ms 348 KB jury found a solution, contestant did not
39 Halted 0 ms 0 KB -