Submission #526496

#	Time	Username	Problem	Language	Result	Execution time	Memory
526496		pokmui9909	Split the Attractions (IOI19_split)	C++17	100 / 100	262 ms	36400 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define x first
#define y second
ll N, M, A, B, C;
vector<ll> G[100005];
vector<ll> T[100005];
vector<ll> NT[100005];
ll visited[100005];
vector<int> ans;
ll idx[100005];
ll par[100005];
ll sz[100005];
vector<pair<ll, ll>> I;
struct UnionFind{
    vector<ll> p;
    UnionFind(ll S){
        p.resize(S + 5, -1);
    }
    ll Find(ll n){
        if (p[n] < 0) return n;
        else return p[n] = Find(p[n]);
    }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[a] += p[b];
        p[b] = a;
    }
    bool Same(ll a, ll b) { return Find(a) == Find(b); }
    ll Size(ll n) { return -p[Find(n)]; }
    void Clear() {fill(p.begin(), p.end(), -1);}
};
ll getSize(ll u, ll p){
    sz[u] = 1;
    for(auto v : T[u]) if(v != p) sz[u] += getSize(v, u);
    return sz[u];
}
ll getCent(ll u, ll p, ll c){
    for(auto v : T[u]) if(v != p && sz[v] * 2 > c) return getCent(v, u, c);
    return u;
}
ll num = 0;
void dfs(ll u){
    num--;
    if(num < 0) return;
    ans[u] = I[1].y;
    for(auto v : G[u]){
        if(ans[v] != 0) continue;
        dfs(v);
    }
}
void dfs2(ll u){
    visited[u] = 1;
    num--;  
    if(num < 0) return;
    ans[u] = I[0].y;
    for(auto v : NT[u]){
        if(visited[v]) continue;
        dfs2(v);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    N = n, M = p.size(), A = a, B = b, C = c;
    ans.resize(N);
    I.push_back({A,1});I.push_back({B,2});I.push_back({C,3});
    sort(I.begin(),I.end());
    A=I[0].x,B=I[1].x,C=I[2].x;
     
    UnionFind uf(N);
    vector<pair<ll, ll>> MST, E;
    for(int i = 0; i < M; i++){
        ll u = p[i], v = q[i];
        G[u].push_back(v);
        G[v].push_back(u);
        if(uf.Same(u, v)){
            E.push_back({u, v});
            continue;
        }
        uf.Union(u, v);
        MST.push_back({u, v});
        T[u].push_back(v);
        T[v].push_back(u);
    }
    uf.Clear();
    getSize(0, -1);
    ll R = getCent(0, -1, N);
    for(int i = 0; i < N; i++){
        for(auto j : T[i]){
            if(i == R || j == R) continue;
            NT[i].push_back(j);
            NT[j].push_back(i);
        }
    }
    getSize(R, -1);
    for(int i = 0; i < MST.size(); i++){
        ll u = MST[i].x, v = MST[i].y;
        if(u == R || v == R) continue;
        uf.Union(u, v);
    }
    ll ok = 0;
    ll NU = -1;
    for(int i = 0; i < N; i++){
        if(i == R) continue;
        if(uf.Size(i) >= A) ok = 1, NU = i;
    }
    ll ok2 = 0;
    if(!ok){
        for(int i = 0; i < E.size(); i++){
            ll u = E[i].x, v = E[i].y;
            if(u == R || v == R) continue;
            uf.Union(u, v);
          	NT[u].push_back(v);
            NT[v].push_back(u);
            if(uf.Size(u) >= A){
                NU = u;
                break;
            }
        }
    }
    if(NU == -1){
        return vector<int>(N, 0);
    }
    num = A;
    visited[R] = 1;
    dfs2(NU);
    assert(num <= 0);
    num = B;
    dfs(R);
    for(int i = 0; i < N; i++){
        if(ans[i] == 0){
            ans[i] = I[2].y;
        }
    }
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i < MST.size(); i++){
      |                    ~~^~~~~~~~~~~~
split.cpp:112:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int i = 0; i < E.size(); i++){
      |                        ~~^~~~~~~~~~
split.cpp:110:8: warning: unused variable 'ok2' [-Wunused-variable]
  110 |     ll ok2 = 0;
      |        ^~~

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