Submission #715724

#	Time	Username	Problem	Language	Result	Execution time	Memory
715724		lmqzzz	Split the Attractions (IOI19_split)	C++14	100 / 100	148 ms	25292 KiB

split

#include "split.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

vector<int> adj[MAXN];
vector<int> g[MAXN];
int num[MAXN], low[MAXN], timer = 0;
int sz[MAXN];
int par[MAXN];
int ans[MAXN];
int color[MAXN];

void dfs(int u, int p) {
        par[u] = p;
        num[u] = low[u] = ++timer;
        sz[u] = 1;
        for (int v : adj[u]) {
                if (v == p) continue;
                if (num[v]) {
                        low[u] = min(low[u], num[v]);
                } else {
                        g[u].emplace_back(v);
                        g[v].emplace_back(u);
                        dfs(v, u);
                        low[u] = min(low[u], low[v]);
                        sz[u] += sz[v];
                }
        }
}

void dfsans(int u, int p, int id, int cur, int& cnt, vector<int>* adj) {
        if (color[u] != cur) return;
        if (cnt == 0) return;
        cnt--;
        color[u] = id;
        for (int v : adj[u]) {
                if (v == p) continue;
                dfsans(v, u, id, cur, cnt, adj);
                if (cnt == 0) return;
        }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
        int aa = a, bb = b, cc = c;
        map<int, int> mp;
        mp[0] = 1;
        mp[1] = 2;
        mp[2] = 3;
        if (a > b) swap(a, b), swap(mp[0], mp[1]);
        if (a > c) swap(a, c), swap(mp[0], mp[2]);
        if (b > c) swap(b, c), swap(mp[1], mp[2]);
        vector<int> res(n, 0);
        int m = p.size();
        for (int i = 0; i < m; i++) {
                adj[p[i]].emplace_back(q[i]);
                adj[q[i]].emplace_back(p[i]);
        }
        dfs(0, -1);
        int best_subtree = -1;
        int best_size = n + 1;
        for (int i = 0; i < n; i++) {
                int subtree_size = sz[i];
                if (subtree_size >= a) {
                        if (subtree_size < best_size) {
                                best_size = subtree_size;
                                best_subtree = i;
                        }
                }
        }

        for (int i = 0; i < n; i++) color[i] = 4;
        int x = 1e9;
        dfsans(best_subtree, par[best_subtree], 3, 4, x, g);

        int notsubtree_size = n - best_size;

        for (int v : g[best_subtree]) {
                if (notsubtree_size >= a) break;
                if (v == par[best_subtree]) continue;
                if (low[v] >= num[best_subtree]) continue;

                notsubtree_size += sz[v];
                best_size -= sz[v];
                dfsans(v, best_subtree, 4, 3, x, g);
        }

        if (notsubtree_size < a) return res;

        if (notsubtree_size >= b) {
                dfsans(0, -1, 1, 4, b, adj);
                dfsans(best_subtree, -1, 0, 3, a, adj);
        } else {
                assert(best_size >= b);
                dfsans(0, -1, 0, 4, a, adj);
                dfsans(best_subtree, -1, 1, 3, b, adj);
        }

        for (int i = 0; i < n; i++) {
                res[i] = mp[min(color[i], 2)];
        }

        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:48:13: warning: unused variable 'aa' [-Wunused-variable]
   48 |         int aa = a, bb = b, cc = c;
      |             ^~
split.cpp:48:21: warning: unused variable 'bb' [-Wunused-variable]
   48 |         int aa = a, bb = b, cc = c;
      |                     ^~
split.cpp:48:29: warning: unused variable 'cc' [-Wunused-variable]
   48 |         int aa = a, bb = b, cc = c;
      |                             ^~

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