Submission #941460

#	Time	Username	Problem	Language	Result	Execution time	Memory
941460		Programmer123	Split the Attractions (IOI19_split)	C++17	40 / 100	1952 ms	19652 KiB

split

#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) {
    auto start_t = clock();
    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::vector<int> children[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;
                children[node].push_back(x);
                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: children[node]) {
                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;
                }
            }
        }
    } else {
        std::mt19937 Rand(std::random_device{}());
        std::uniform_int_distribution dist(0, n - 1);
        while (clock() - start_t <= 1.95 * CLOCKS_PER_SEC) {
            if (Rand() % 2) {
                int root = dist(Rand);
                for (int i = 0; i < n; ++i) {
                    std::shuffle(connections[i].begin(), connections[i].end(), std::default_random_engine(Rand()));
                }
                int size[n];
                int parent[n];
                std::vector<int> children[n];
                bool seen[n];
                for (int i = 0; i < n; ++i) {
                    seen[i] = false;
                }
                std::function<void(int)> Root = [&](int node) {
                    parent[node] = node;
                    seen[node] = true;
                    if (Rand() % 2) {
                        std::queue<int> queue;
                        queue.push(node);
                        while (!queue.empty()) {
                            auto next = queue.front();
                            queue.pop();
                            for (auto x: connections[next]) {
                                if (seen[x]) continue;
                                seen[x] = true;
                                parent[x] = next;
                                children[next].push_back(x);
                                queue.push(x);
                            }
                        }
                    } else {
                        std::stack<int> queue;
                        queue.push(node);
                        while (!queue.empty()) {
                            auto next = queue.top();
                            queue.pop();
                            for (auto x: connections[next]) {
                                if (seen[x]) continue;
                                seen[x] = true;
                                parent[x] = next;
                                children[next].push_back(x);
                                queue.push(x);
                            }
                        }
                    }
//                seen[node] = true;
//                parent[node] = from;
//                int res = 1;
//                for (auto x: connections[node]) {
//                    if (seen[x]) continue;
//                    children[node].push_back(x);
//                    res += dfs(x, node);
//                }
//                return size[node] = res;
                };
                std::function<int(int, int)> oldroot = [&](int node, int from) {
                    seen[node] = true;
                    parent[node] = from;
                    int res = 1;
                    for (auto x: connections[node]) {
                        if (seen[x]) continue;
                        children[node].push_back(x);
                        res += oldroot(x, node);
                    }
                    return size[node] = res;
                };
                std::function<int(int)> dfs = [&](int node) {
                    int s = 1;
                    for (auto x: children[node]) {
                        s += dfs(x);
                    }
                    return size[node] = s;
                };
                if (Rand() % 2) {
                    Root(root);
                    dfs(root);
                } else {
                    oldroot(root, root);
                }
                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: children[node]) {
                        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;
                        }
                    }
                }
            } else {
                int num1, t1, num2, t2;
                do {
                    switch (Rand() % 3) {
                        case 0:
                            num1 = a;
                            t1 = 1;
                            break;
                        case 1:
                            num1 = b;
                            t1 = 2;
                            break;
                        case 2:
                            num1 = c;
                            t1 = 3;
                            break;
                    }
                    switch (Rand() % 3) {
                        case 0:
                            num2 = a;
                            t2 = 1;
                            break;
                        case 1:
                            num2 = b;
                            t2 = 2;
                            break;
                        case 2:
                            num2 = c;
                            t2 = 3;
                            break;
                    }
                } while (t1 == t2);
                int r1, r2;
                do {
                    r1 = Rand() % n;
                    r2 = Rand() % n;
                } while (r1 == r2);
                num1--;
                num2--;
                res[r1] = t1;
                res[r2] = t2;
                std::queue<int> q1, q2;
                q1.push(r1);
                q2.push(r2);
                while (true) {
                    if (num1 + num2 == 0) {
                        for (int i = 0; i < n; ++i) {
                            if (res[i] == 0) res[i] = 6 - t1 - t2;
                        }
                        return res;
                    }
                    if (num1 && q1.empty()) {
                        break;
                    }
                    if (num2 && q2.empty()) {
                        break;
                    }
                    if (num1 > num2) {
                        auto next = q1.front();
                        q1.pop();
                        for (auto x: connections[next]) {
                            if (!num1) break;
                            if (res[x] != 0) break;
                            res[x] = t1;
                            num1--;
                            q1.push(x);
                        }
                    } else {
                        auto next = q2.front();
                        q2.pop();
                        for (auto x: connections[next]) {
                            if (!num2) break;
                            if (res[x] != 0) break;
                            res[x] = t2;
                            num2--;
                            q2.push(x);
                        }
                    }
                }
                res = std::vector<int>(n);
            }
        }
    }
    return res;
}

Compilation message (stderr)

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

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