Submission #941440

#	Time	Username	Problem	Language	Result	Execution time	Memory
941440		Programmer123	Split the Attractions (IOI19_split)	C++17	40 / 100	1900 ms	19656 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.9 * CLOCKS_PER_SEC) {
            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];
            std::function<void(int)> Root = [&](int node) {
                bool seen[n];
                for (int i = 0; i < n; ++i) {
                    seen[i] = false;
                }
                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)> dfs = [&](int node) {
                int s = 1;
                for (auto x: children[node]) {
                    s += dfs(x);
                }
                return size[node] = s;
            };
            Root(root);
            dfs(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;
                    }
                }
            }
        }
    }
    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