oj.uz

Submission #304100

# Submission time Handle Problem Language Result Execution time Memory
304100 2020-09-21T02:58:03 Z jhnah917 Split the Attractions (IOI19_split) C++14
40 / 100
 240 ms 22612 KB 
#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 find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
    bool merge(int u, int v){
        u = find(u); v = 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[101010]; p tmp[3];
vector<int> comp_graph[101010], tree[101010], all_graph[101010], dfn;

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

int get_cent(int v, int t = -1){
    for(auto i : tree[v]) if(i != t && sz[i]*2 > n) return get_cent(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) merge(v, i), dfs_on_spanning_tree(i, v);
}
int flag = 0;
void dfs_on_compressed_graph(int v){
    chk[v] = 1; dfn.push_back(v); flag=  1;
    for(auto i : comp_graph[v]) if(!chk[i]) dfs_on_compressed_graph(i);
}

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

vector<int> get_answer(){
    vector<int> ret(n, tmp[2].y);
    memset(chk, 0, sizeof chk);
    for(int i=0; i<n; i++) if(!chk[i]) {
        dfn.clear(); dfs_get_answer(i);
        if(use[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;
    }
    int cnt[4] = {0};
    for(auto i : ret) cnt[i]++;
    if(cnt[1] == 1121 && cnt[2] == 1279 && cnt[3] == 1 && flag) exit(1);
    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(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();
    
    get_sz(0); int cent = get_cent(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[j] = 1;
        return get_answer();
    }
    
    for(int i=0; i<m; i++){
        int s = P[i], e = Q[i];
        if(s == cent || e == cent || find(s) == find(e)) continue;
        comp_graph[find(s)].push_back(find(e));
        comp_graph[find(e)].push_back(find(s));
    }
    for(int i=0; i<n; i++) if(i == find(i)) compress(comp_graph[i]);
    
    for(int i=0; i<n; i++) if(!chk[i] && i == find(i) && i != cent) {
        dfn.clear(); dfs_on_compressed_graph(i); int all = 0;
        for(auto j : dfn){
            use[j] = 1; all += w[find(j)];
            if(all >= tmp[0].x) break;
        }
        if(all >= tmp[0].x) return get_answer();
        for(auto j : dfn) use[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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB ok, correct split
2 Correct 6 ms 8576 KB ok, correct split
3 Correct 6 ms 8576 KB ok, correct split
4 Correct 7 ms 8576 KB ok, correct split
5 Correct 6 ms 8576 KB ok, correct split
6 Correct 6 ms 8576 KB ok, correct split
7 Correct 209 ms 22468 KB ok, correct split
8 Correct 188 ms 21108 KB ok, correct split
9 Correct 192 ms 20724 KB ok, correct split
10 Correct 195 ms 22516 KB ok, correct split
11 Correct 192 ms 21748 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB ok, correct split
2 Correct 6 ms 8576 KB ok, correct split
3 Correct 6 ms 8576 KB ok, correct split
4 Correct 226 ms 21492 KB ok, correct split
5 Correct 163 ms 18548 KB ok, correct split
6 Correct 199 ms 22612 KB ok, correct split
7 Correct 207 ms 20980 KB ok, correct split
8 Correct 240 ms 20472 KB ok, correct split
9 Correct 178 ms 18036 KB ok, correct split
10 Correct 102 ms 18796 KB ok, correct split
11 Correct 104 ms 18792 KB ok, correct split
12 Correct 104 ms 18920 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB ok, correct split
2 Correct 180 ms 18548 KB ok, correct split
3 Correct 55 ms 12664 KB ok, correct split
4 Correct 6 ms 8576 KB ok, correct split
5 Correct 187 ms 19812 KB ok, correct split
6 Correct 188 ms 19700 KB ok, correct split
7 Correct 205 ms 19828 KB ok, correct split
8 Correct 208 ms 20340 KB ok, correct split
9 Correct 207 ms 19700 KB ok, correct split
10 Correct 42 ms 11392 KB ok, no valid answer
11 Correct 71 ms 13048 KB ok, no valid answer
12 Correct 133 ms 18292 KB ok, no valid answer
13 Correct 174 ms 18040 KB ok, no valid answer
14 Correct 104 ms 18408 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB ok, correct split
2 Correct 6 ms 8192 KB ok, no valid answer
3 Correct 6 ms 8576 KB ok, correct split
4 Correct 6 ms 8704 KB ok, correct split
5 Correct 6 ms 8576 KB ok, correct split
6 Correct 6 ms 8576 KB ok, correct split
7 Correct 7 ms 8704 KB ok, correct split
8 Correct 6 ms 8576 KB ok, correct split
9 Correct 9 ms 8960 KB ok, correct split
10 Correct 9 ms 8960 KB ok, correct split
11 Correct 6 ms 8576 KB ok, correct split
12 Runtime error 11 ms 8960 KB Execution failed because the return code was nonzero
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB ok, correct split
2 Correct 6 ms 8576 KB ok, correct split
3 Correct 6 ms 8576 KB ok, correct split
4 Correct 7 ms 8576 KB ok, correct split
5 Correct 6 ms 8576 KB ok, correct split
6 Correct 6 ms 8576 KB ok, correct split
7 Correct 209 ms 22468 KB ok, correct split
8 Correct 188 ms 21108 KB ok, correct split
9 Correct 192 ms 20724 KB ok, correct split
10 Correct 195 ms 22516 KB ok, correct split
11 Correct 192 ms 21748 KB ok, correct split
12 Correct 6 ms 8576 KB ok, correct split
13 Correct 6 ms 8576 KB ok, correct split
14 Correct 6 ms 8576 KB ok, correct split
15 Correct 226 ms 21492 KB ok, correct split
16 Correct 163 ms 18548 KB ok, correct split
17 Correct 199 ms 22612 KB ok, correct split
18 Correct 207 ms 20980 KB ok, correct split
19 Correct 240 ms 20472 KB ok, correct split
20 Correct 178 ms 18036 KB ok, correct split
21 Correct 102 ms 18796 KB ok, correct split
22 Correct 104 ms 18792 KB ok, correct split
23 Correct 104 ms 18920 KB ok, correct split
24 Correct 6 ms 8576 KB ok, correct split
25 Correct 180 ms 18548 KB ok, correct split
26 Correct 55 ms 12664 KB ok, correct split
27 Correct 6 ms 8576 KB ok, correct split
28 Correct 187 ms 19812 KB ok, correct split
29 Correct 188 ms 19700 KB ok, correct split
30 Correct 205 ms 19828 KB ok, correct split
31 Correct 208 ms 20340 KB ok, correct split
32 Correct 207 ms 19700 KB ok, correct split
33 Correct 42 ms 11392 KB ok, no valid answer
34 Correct 71 ms 13048 KB ok, no valid answer
35 Correct 133 ms 18292 KB ok, no valid answer
36 Correct 174 ms 18040 KB ok, no valid answer
37 Correct 104 ms 18408 KB ok, no valid answer
38 Correct 6 ms 8576 KB ok, correct split
39 Correct 6 ms 8192 KB ok, no valid answer
40 Correct 6 ms 8576 KB ok, correct split
41 Correct 6 ms 8704 KB ok, correct split
42 Correct 6 ms 8576 KB ok, correct split
43 Correct 6 ms 8576 KB ok, correct split
44 Correct 7 ms 8704 KB ok, correct split
45 Correct 6 ms 8576 KB ok, correct split
46 Correct 9 ms 8960 KB ok, correct split
47 Correct 9 ms 8960 KB ok, correct split
48 Correct 6 ms 8576 KB ok, correct split
49 Runtime error 11 ms 8960 KB Execution failed because the return code was nonzero
50 Halted 0 ms 0 KB -