Submission #314660

#	Time	Username	Problem	Language	Result	Execution time	Memory
314660		apostoldaniel854	Split the Attractions (IOI19_split)	C++14	40 / 100	169 ms	22392 KiB

split

#include <bits/stdc++.h>

using namespace std;

#include "split.h"
//#define HOME

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " < x << "\n"
const int N = 1e5;
vector <pair <int, int>> order;
bool viz[N];
vector <int> gr[N], arb[N];
int sz[N];
void dfsPrec (int node) {
    viz[node] = true;
    sz[node] = 1;
    for (int vec : gr[node])
        if (not viz[vec]) {
            arb[node].pb (vec);
            arb[vec].pb (node);
            dfsPrec (vec);
            sz[node] += sz[vec];
        }
}
int findCentroid (int node, int par) {
    for (int son : arb[node])
        if (son != par && sz[son] * 2 >= sz[0])
            return findCentroid (son, node);
    return node;
}
int in[N], out[N];
int t;
void dfsReroot (int node, int par) {
    sz[node] = 1;
    in[node] = ++t;
    for (int son : arb[node])
        if (son != par) {
            dfsReroot (son, node);
            sz[node] += sz[son];
        }
    out[node] = ++t;
}
vector <int> ans;

void buildAns (int node, int par, int pivot) {
    if (in[pivot] <= in[node] && out[node] <= out[pivot]) {
        if (order[0].first) {
            ans[node] = order[0].second;
            order[0].first--;
        }
    }
    else {
        if (order[1].first) {
            ans[node] = order[1].second;
            order[1].first--;
        }
    }
    for (int son : arb[node])
        if (son != par)
            buildAns (son, node, pivot);
}

vector <int> find_split (int n, int a, int b, int c, vector <int> p, vector <int> q) {
    order.pb ({a, 1});
    order.pb ({b, 2});
    order.pb ({c, 3});
    ans.resize (n, 0);
    sort (order.begin (), order.end ());
    for (int i = 0; i < p.size (); i++) {
        gr[p[i]].pb (q[i]);
        gr[q[i]].pb (p[i]);
    }
    dfsPrec (0);
    int root = findCentroid (0, -1);
    dfsReroot (root, -1);
    int pivot = -1;
    for (int i = 0; i < n; i++)
        if (sz[i] >= order[0].first && sz[i] <= order[0].first + order[2].first)
            pivot = i;
    if (pivot == -1)
        return ans;
    ans.clear ();
    ans.resize (n, order[2].second);
    buildAns (root, -1, pivot);
    return ans;
}
#ifdef HOME
int main () {
    int n, m, a, b, c;
    cin >> n >> m;
    cin >> a >> b >> c;
    vector <int> p (m), q (m);
    for (int i = 0; i < m; i++)
        cin >> p[i] >> q[i];
    vector <int> ans = find_split (n, a, b, c, p, q);
    for (int x : ans)
        cout << x << " ";
    cout << "\n";
    return 0;
}
#endif
/**
    6 5
    2 2 2
    0 1
    1 2
    2 3
    3 4
    4 5
**/

Compilation message (stderr)

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

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