Submission #304208

#	Time	Username	Problem	Language	Result	Execution time	Memory
304208		jhnah917	Split the Attractions (IOI19_split)	C++14	40 / 100	239 ms	22520 KiB

split

#ifndef LOCAL
#include "split.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef pair<int, int> p;

namespace UnionFind{
    int par[101010], w[101010];
    void uf_init(){ iota(par, par+101010, 0); fill(w, w+101010, 1); }
    int uf_find(int v){ return v == par[v] ? v : par[v] = uf_find(par[v]); }
    bool uf_merge(int u, int v){
        u = uf_find(u); v = uf_find(v);
        if(u == v) return 0;
        par[u] = v; w[v] += w[u]; return 1;
    }
}
using namespace UnionFind;

int n, m, a, b, c, sz[101010], chk[101010], use_at_answer[101010]; p tmp[3];
vector<int> comp_graph[101010], tree[101010], all_graph[101010], dfn;

int dfs_get_size(int v, int t = -1){
    sz[v] = 1;
    for(auto i : tree[v]) if(i != t) sz[v] += dfs_get_size(i, v);
    return sz[v];
}

int dfs_get_centroid(int v, int t = -1){
    for(auto i : tree[v]) if(i != t && sz[i]*2 >= n) return dfs_get_centroid(i, v);
    return v;
}

void dfs_on_spanning_tree(int v, int t = -1){
    dfn.push_back(v);
    for(auto i : tree[v]) if(i != t) uf_merge(v, i), dfs_on_spanning_tree(i, v);
}

void dfs_on_compressed_graph(int v){
    chk[v] = 1; dfn.push_back(v);
    for(auto i : comp_graph[v]) if(!chk[i]) dfs_on_compressed_graph(i);
}

void dfs_on_all_graph(int v){
    chk[v] = 1; dfn.push_back(v);
    for(auto i : all_graph[v]) if(!chk[i] && use_at_answer[v] == use_at_answer[i]) dfs_on_all_graph(i);
}

vector<int> get_answer(){
    vector<int> ret(n, tmp[2].y);
    for(auto i : dfn) if(!use_at_answer[i]) exit(1);
    memset(chk, 0, sizeof chk);
    for(int i=0; i<n; i++) if(!chk[i]) {
        dfn.clear(); dfs_on_all_graph(i);
        if(use_at_answer[i]) for(int j=0; j < tmp[0].x; j++) ret[dfn[j]] = tmp[0].y;
        else for(int j=0; j<tmp[1].x; j++) ret[dfn[j]] = tmp[1].y;
    }
    return ret;
}

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;
    tmp[0] = p(a, 1); tmp[1] = p(b, 2); tmp[2] = p(c, 3); sort(tmp, tmp+3);
    uf_init();
    for(int i=0; i<m; i++){
        int s = P[i], e = Q[i];
        if(uf_merge(s, e)) tree[s].push_back(e), tree[e].push_back(s);
        all_graph[s].push_back(e); all_graph[e].push_back(s);
    }
    uf_init();
    
    dfs_get_size(0); int cent = dfs_get_centroid(0);
    for(auto i : tree[cent]){
        dfn.clear(); dfs_on_spanning_tree(i, cent);
        if(dfn.size() < tmp[0].x) continue;
        for(auto j : dfn) use_at_answer[j] = 1;
        return get_answer();
    }
    
    for(int i=0; i<m; i++){
        int s = P[i], e = Q[i];
        if(s == cent || e == cent || uf_find(s) == uf_find(e)) continue;
        comp_graph[uf_find(s)].push_back(uf_find(e));
        comp_graph[uf_find(e)].push_back(uf_find(s));
    }
    for(int i=0; i<n; i++) if(i == uf_find(i)) compress(comp_graph[i]);
    
    for(int i=0; i<n; i++) if(!chk[i] && i == uf_find(i) && i != cent) {
        dfn.clear(); dfs_on_compressed_graph(i); int all = 0;
        for(auto j : dfn){
            use_at_answer[j] = 1; all += w[uf_find(j)];
            if(all >= tmp[0].x) break;
        }
        if(all >= tmp[0].x) return get_answer();
        for(auto j : dfn) use_at_answer[j] = 0;
    }
    return vector<int>(n, 0);
}

#ifdef LOCAL
int main() {
    int n, m, a, b, c;
    assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
    vector<int> p(m), q(m);
    for (int i=0; i<m; i++) assert(2 == scanf("%d%d", &p[i], &q[i]));
    
    vector<int> result = find_split(n, a, b, c, p, q);
    
    for (int i=0; i<(int)result.size(); i++) printf("%s%d", ((i>0)?" ":""), result[i]);
    printf("\n");
    return 0;
}
#endif

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:80:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |         if(dfn.size() < tmp[0].x) continue;
      |                       ^

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