Submission #499229

#	Time	Username	Problem	Language	Result	Execution time	Memory
499229		InternetPerson10	Split the Attractions (IOI19_split)	C++17	100 / 100	121 ms	15588 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

struct dsu {
    vector<int> par, siz;
    void init(int n) {
        vector<int>().swap(par);
        vector<int>().swap(siz);
        par.resize(n);
        siz.resize(n);
        for(int i = 0; i < n; i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }
    int get(int x) {
        if(x == par[x]) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x); y = get(y);
        if(x == y) return false;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

dsu uf;

vector<vector<int>> adj;
vector<int> an, sub;

int dfs(int n, int par = -1) {
    if(adj.size() == 1 && par != -1) {
        return sub[n] = 1;
    }
    int ans = 1;
    for(int ch : adj[n]) {
        if(ch == par) continue;
        ans += dfs(ch, n);
    }
    return sub[n] = ans;
}

int tar, red = -1;

void dfs_red(int n, int par = -1) {
    if(uf.get(n) != red) {
        if(par == -1) {
            while(true) {}
        }
        return;
    }
    if(an[n]) return; 
    if(!tar) return;
    tar--;
    an[n] = 4;
    for(int ch : adj[n]) {
        if(ch == par) continue;
        dfs_red(ch, n);
    }
}

void dfs_ans(int n, int par = -1) {
    if(an[n]) return; 
    if(!tar) return;
    tar--;
    an[n] = 4;
    for(int ch : adj[n]) {
        if(ch == par) continue;
        dfs_ans(ch, n);
    }
}

int find_centroid(int n, int par = -1) {
    if(par == -1) {
        for(int ch : adj[n]) {
            if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
        }
    }
    for(int ch : adj[n]) {
        if(ch == par) continue;
        if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
    }
    return n;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int x = 1, y = 2, z = 3;
    int m = p.size();
    if(a > b) {
        swap(a, b);
        swap(x, y);
    }
    if(b > c) {
        swap(b, c);
        swap(y, z);
    }
    if(a > b) {
        swap(a, b);
        swap(x, y);
    }
    adj.resize(n);
    sub.resize(n);
    uf.init(n);
    for(int i = 0; i < m; i++) {
        if(uf.unite(p[i], q[i])) {
            adj[p[i]].push_back(q[i]);
            adj[q[i]].push_back(p[i]);
            p[i] = q[i] = -1;
        }
    }
    dfs(0);
    int k = find_centroid(0);
    dfs(k);
    uf.init(n);
    for(int i = 0; i < adj.size(); i++) {
        for(int j : adj[i]) {
            if(i != k && j != k) {
                uf.unite(i, j);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(i == k) continue;
        if(a <= uf.siz[uf.get(i)]) {
            red = uf.get(i);
            break;
        }
    }
    for(int i = 0; i < m && (red == -1); i++) {
        if(p[i] != -1 && p[i] != k && q[i] != k) {
            uf.unite(p[i], q[i]);
            adj[p[i]].push_back(q[i]);
            adj[q[i]].push_back(p[i]);
            if(a <= uf.siz[uf.get(p[i])]) {
                red = uf.get(p[i]);
            }
        }
    }
    assert(uf.siz[k] == 1);
    an.resize(n, 0);
    if(red == -1) return an;
    for(int i = 0; i < n; i++) {
        if(uf.get(i) == red) {
            tar = a;
            dfs_red(i);
            break;
        }
        if(i == n-1) {
            assert(false);
        }
    }
    for(int i = 0; i < n; i++) {
        if(an[i] == 4) an[i] = x;
    }
    /*
    cout << x << ' ' << y << ' ' << z << '\n';
    cout << a << ' ' << b << ' ' << c << '\n';
    for(int i = 0; i < n; i++) cout << an[i] << ' ';
    cout << '\n';
    for(int i = 0; i < n; i++) cout << uf.get(i) << ' ';
    cout << '\n';
    */
    tar = b;
    dfs_ans(k);
    assert(tar == 0);
    for(int i = 0; i < n; i++) {
        if(an[i] == 4) an[i] = y;
        if(an[i] == 0) an[i] = z;
    }
    for(int i = 0; i < n; i++) {
        if(an[i] == x) a--;
        if(an[i] == y) b--;
        if(an[i] == z) c--;
    }
    return an;
}

Compilation message (stderr)

split.cpp: In function 'int find_centroid(int, int)':
split.cpp:82:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
split.cpp:87:20: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         if(sub[ch] > sub.size()/2) return find_centroid(ch, n);
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i = 0; i < adj.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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