oj.uz

답안 #385654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385654 2021-04-04T16:51:12 Z jhnah917 Split the Attractions (IOI19_split) C++14
100 / 100
 299 ms 25824 KB 
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;

constexpr int SZ = 101010;

template<size_t _Sz> struct UnionFind {
    int P[_Sz], W[_Sz];
    UnionFind(){ clear(); }
    void clear(){ iota(P, P+_Sz, 0); fill(W, W+_Sz, 1); }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return false;
        P[u] = v; W[v] += W[u];
        return true;
    }
};

int N, M, A, B, C, S[SZ], chk[SZ];
PII ORD[3];
vector<int> G[SZ], Tree[SZ], Comp[SZ];
UnionFind<SZ> UF;

int get_sz(int v, int b=-1){
    S[v] = 1;
    for(auto i : Tree[v]) if(i != b) S[v] += get_sz(i, v);
    return S[v];
}
int get_cent(int v, int tot, int b=-1){
    for(auto i : Tree[v]) if(i != b && S[i]*2 > tot) return get_cent(i, tot, v);
    return v;
}

vector<int> dfs_subtree(int v, int b){
    vector<int> ret;
    function<void(int,int)> go = [&go,&ret](int v, int b){
        ret.push_back(v);
        for(auto i : Tree[v]) if(i != b) go(i, v);
    };
    go(v, b);
    return ret;
}

void dfs_merge(int v, int b){
    for(auto i : Tree[v]) if(i != b) UF.merge(v, i), dfs_merge(i, v);
}

vector<int> dfs_comp(int v){
    vector<int> ret;
    function<void(int)> go = [&go,&ret](int v){
        chk[v] = 1; ret.push_back(v);
        for(auto i : Comp[v]) if(!chk[i]) go(i);
    };
    go(v);
    return ret;
}

int use[SZ];
vector<int> dfs_graph(int v){
    vector<int> ret;
    function<void(int)> go = [&ret,&go](int v){
        chk[v] = 1; ret.push_back(v);
        for(auto i : G[v]) if(!chk[i] && use[v] == use[i]) go(i);
    };
    go(v);
    return ret;
}

vector<int> get_answer(const vector<int> &V){
    vector<int> res(N, ORD[2].y);
    memset(chk, 0, sizeof chk);

    for(auto i : V) use[i] = 1;
    for(int i=0; i<N; i++){
        if(chk[i]) continue;
        auto dfn = dfs_graph(i);
        dfn.resize(ORD[!use[i]].x);
        for(auto j : dfn) res[j] = ORD[!use[i]].y;
    }
    return res;
}

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;
    ORD[0] = {A, 1}; ORD[1] = {B, 2}; ORD[2] = {C, 3};
    sort(ORD, ORD+3);

    UF.clear();
    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);
        G[s].push_back(e); G[e].push_back(s);
    }

    int cent = get_cent(0, get_sz(0));
    for(auto i : Tree[cent]){
        auto dfn = dfs_subtree(i, cent);
        if(dfn.size() >= ORD[0].x) return get_answer(dfn);
    }

    UF.clear();
    for(auto i : Tree[cent]) dfs_merge(i, cent);
    for(int i=0; i<M; i++){
        int s = UF.find(p[i]), e = UF.find(q[i]);
        if(s == cent || e == cent || s == e) continue;
        Comp[s].push_back(e); Comp[e].push_back(s);
    }

    memset(chk, 0, sizeof chk);
    for(int i=0; i<N; i++){
        if(i == cent || i != UF.find(i) || chk[i]) continue;
        auto dfn = dfs_comp(i);

        set<int> st;
        int sum = 0;
        for(auto j : dfn){
            sum += UF.W[j];
            st.insert(j);
            if(sum >= ORD[0].x) break;
        }
        if(sum < ORD[0].x) continue;

        vector<int> res;
        for(int j=0; j<N; j++) if(st.count(UF.find(j))) res.push_back(j);
        return get_answer(res);
    }
    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:117:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |         if(dfn.size() >= ORD[0].x) return get_answer(dfn);
      |                       ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8684 KB ok, correct split
2 Correct 7 ms 8684 KB ok, correct split
3 Correct 7 ms 8684 KB ok, correct split
4 Correct 7 ms 8684 KB ok, correct split
5 Correct 7 ms 8684 KB ok, correct split
6 Correct 7 ms 8684 KB ok, correct split
7 Correct 193 ms 24228 KB ok, correct split
8 Correct 165 ms 22436 KB ok, correct split
9 Correct 167 ms 22180 KB ok, correct split
10 Correct 193 ms 24356 KB ok, correct split
11 Correct 172 ms 23332 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8684 KB ok, correct split
2 Correct 7 ms 8684 KB ok, correct split
3 Correct 7 ms 8684 KB ok, correct split
4 Correct 192 ms 22248 KB ok, correct split
5 Correct 140 ms 18536 KB ok, correct split
6 Correct 200 ms 24356 KB ok, correct split
7 Correct 184 ms 22308 KB ok, correct split
8 Correct 197 ms 20456 KB ok, correct split
9 Correct 163 ms 18280 KB ok, correct split
10 Correct 94 ms 18780 KB ok, correct split
11 Correct 96 ms 18780 KB ok, correct split
12 Correct 92 ms 18780 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8684 KB ok, correct split
2 Correct 189 ms 18580 KB ok, correct split
3 Correct 44 ms 12788 KB ok, correct split
4 Correct 7 ms 8832 KB ok, correct split
5 Correct 165 ms 21028 KB ok, correct split
6 Correct 172 ms 20900 KB ok, correct split
7 Correct 172 ms 20940 KB ok, correct split
8 Correct 173 ms 21324 KB ok, correct split
9 Correct 172 ms 20812 KB ok, correct split
10 Correct 43 ms 11628 KB ok, no valid answer
11 Correct 62 ms 13036 KB ok, no valid answer
12 Correct 123 ms 17896 KB ok, no valid answer
13 Correct 162 ms 17796 KB ok, no valid answer
14 Correct 114 ms 18012 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8684 KB ok, correct split
2 Correct 7 ms 8684 KB ok, no valid answer
3 Correct 7 ms 8684 KB ok, correct split
4 Correct 7 ms 8684 KB ok, correct split
5 Correct 7 ms 8684 KB ok, correct split
6 Correct 6 ms 8684 KB ok, correct split
7 Correct 6 ms 8684 KB ok, correct split
8 Correct 8 ms 8684 KB ok, correct split
9 Correct 11 ms 8940 KB ok, correct split
10 Correct 9 ms 8940 KB ok, correct split
11 Correct 7 ms 8684 KB ok, correct split
12 Correct 10 ms 8940 KB ok, correct split
13 Correct 6 ms 8684 KB ok, correct split
14 Correct 7 ms 8684 KB ok, correct split
15 Correct 6 ms 8684 KB ok, correct split
16 Correct 6 ms 8684 KB ok, correct split
17 Correct 7 ms 8704 KB ok, correct split
18 Correct 8 ms 8684 KB ok, correct split
19 Correct 8 ms 8684 KB ok, correct split
20 Correct 8 ms 8684 KB ok, correct split
21 Correct 8 ms 8940 KB ok, correct split
22 Correct 9 ms 8940 KB ok, correct split
23 Correct 8 ms 8940 KB ok, correct split
24 Correct 8 ms 8940 KB ok, correct split
25 Correct 9 ms 8940 KB ok, correct split
26 Correct 9 ms 8940 KB ok, correct split
27 Correct 11 ms 9068 KB ok, correct split
28 Correct 9 ms 8940 KB ok, correct split
29 Correct 7 ms 8684 KB ok, correct split
30 Correct 9 ms 8940 KB ok, correct split
31 Correct 7 ms 8684 KB ok, correct split
32 Correct 8 ms 8684 KB ok, correct split
33 Correct 7 ms 8684 KB ok, correct split
34 Correct 9 ms 8940 KB ok, correct split
35 Correct 9 ms 8940 KB ok, correct split
36 Correct 9 ms 8812 KB ok, correct split
37 Correct 10 ms 8940 KB ok, correct split
38 Correct 11 ms 9068 KB ok, correct split
39 Correct 11 ms 8940 KB ok, correct split
40 Correct 10 ms 8940 KB ok, correct split
41 Correct 8 ms 8812 KB ok, correct split
42 Correct 8 ms 8812 KB ok, correct split
43 Correct 11 ms 8940 KB ok, correct split
44 Correct 9 ms 8940 KB ok, correct split
45 Correct 9 ms 8940 KB ok, correct split
46 Correct 9 ms 8940 KB ok, correct split
47 Correct 10 ms 9080 KB ok, no valid answer
48 Correct 11 ms 8940 KB ok, correct split
49 Correct 9 ms 8940 KB ok, correct split
50 Correct 7 ms 8684 KB ok, no valid answer
51 Correct 7 ms 8684 KB ok, no valid answer
52 Correct 9 ms 8940 KB ok, no valid answer
53 Correct 10 ms 8940 KB ok, no valid answer
54 Correct 9 ms 8940 KB ok, no valid answer
55 Correct 10 ms 8940 KB ok, no valid answer
56 Correct 9 ms 8940 KB ok, no valid answer

Subtask #5
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8684 KB ok, correct split
2 Correct 7 ms 8684 KB ok, correct split
3 Correct 7 ms 8684 KB ok, correct split
4 Correct 7 ms 8684 KB ok, correct split
5 Correct 7 ms 8684 KB ok, correct split
6 Correct 7 ms 8684 KB ok, correct split
7 Correct 193 ms 24228 KB ok, correct split
8 Correct 165 ms 22436 KB ok, correct split
9 Correct 167 ms 22180 KB ok, correct split
10 Correct 193 ms 24356 KB ok, correct split
11 Correct 172 ms 23332 KB ok, correct split
12 Correct 8 ms 8684 KB ok, correct split
13 Correct 7 ms 8684 KB ok, correct split
14 Correct 7 ms 8684 KB ok, correct split
15 Correct 192 ms 22248 KB ok, correct split
16 Correct 140 ms 18536 KB ok, correct split
17 Correct 200 ms 24356 KB ok, correct split
18 Correct 184 ms 22308 KB ok, correct split
19 Correct 197 ms 20456 KB ok, correct split
20 Correct 163 ms 18280 KB ok, correct split
21 Correct 94 ms 18780 KB ok, correct split
22 Correct 96 ms 18780 KB ok, correct split
23 Correct 92 ms 18780 KB ok, correct split
24 Correct 7 ms 8684 KB ok, correct split
25 Correct 189 ms 18580 KB ok, correct split
26 Correct 44 ms 12788 KB ok, correct split
27 Correct 7 ms 8832 KB ok, correct split
28 Correct 165 ms 21028 KB ok, correct split
29 Correct 172 ms 20900 KB ok, correct split
30 Correct 172 ms 20940 KB ok, correct split
31 Correct 173 ms 21324 KB ok, correct split
32 Correct 172 ms 20812 KB ok, correct split
33 Correct 43 ms 11628 KB ok, no valid answer
34 Correct 62 ms 13036 KB ok, no valid answer
35 Correct 123 ms 17896 KB ok, no valid answer
36 Correct 162 ms 17796 KB ok, no valid answer
37 Correct 114 ms 18012 KB ok, no valid answer
38 Correct 7 ms 8684 KB ok, correct split
39 Correct 7 ms 8684 KB ok, no valid answer
40 Correct 7 ms 8684 KB ok, correct split
41 Correct 7 ms 8684 KB ok, correct split
42 Correct 7 ms 8684 KB ok, correct split
43 Correct 6 ms 8684 KB ok, correct split
44 Correct 6 ms 8684 KB ok, correct split
45 Correct 8 ms 8684 KB ok, correct split
46 Correct 11 ms 8940 KB ok, correct split
47 Correct 9 ms 8940 KB ok, correct split
48 Correct 7 ms 8684 KB ok, correct split
49 Correct 10 ms 8940 KB ok, correct split
50 Correct 6 ms 8684 KB ok, correct split
51 Correct 7 ms 8684 KB ok, correct split
52 Correct 6 ms 8684 KB ok, correct split
53 Correct 6 ms 8684 KB ok, correct split
54 Correct 7 ms 8704 KB ok, correct split
55 Correct 8 ms 8684 KB ok, correct split
56 Correct 8 ms 8684 KB ok, correct split
57 Correct 8 ms 8684 KB ok, correct split
58 Correct 8 ms 8940 KB ok, correct split
59 Correct 9 ms 8940 KB ok, correct split
60 Correct 8 ms 8940 KB ok, correct split
61 Correct 8 ms 8940 KB ok, correct split
62 Correct 9 ms 8940 KB ok, correct split
63 Correct 9 ms 8940 KB ok, correct split
64 Correct 11 ms 9068 KB ok, correct split
65 Correct 9 ms 8940 KB ok, correct split
66 Correct 7 ms 8684 KB ok, correct split
67 Correct 9 ms 8940 KB ok, correct split
68 Correct 7 ms 8684 KB ok, correct split
69 Correct 8 ms 8684 KB ok, correct split
70 Correct 7 ms 8684 KB ok, correct split
71 Correct 9 ms 8940 KB ok, correct split
72 Correct 9 ms 8940 KB ok, correct split
73 Correct 9 ms 8812 KB ok, correct split
74 Correct 10 ms 8940 KB ok, correct split
75 Correct 11 ms 9068 KB ok, correct split
76 Correct 11 ms 8940 KB ok, correct split
77 Correct 10 ms 8940 KB ok, correct split
78 Correct 8 ms 8812 KB ok, correct split
79 Correct 8 ms 8812 KB ok, correct split
80 Correct 11 ms 8940 KB ok, correct split
81 Correct 9 ms 8940 KB ok, correct split
82 Correct 9 ms 8940 KB ok, correct split
83 Correct 9 ms 8940 KB ok, correct split
84 Correct 10 ms 9080 KB ok, no valid answer
85 Correct 11 ms 8940 KB ok, correct split
86 Correct 9 ms 8940 KB ok, correct split
87 Correct 7 ms 8684 KB ok, no valid answer
88 Correct 7 ms 8684 KB ok, no valid answer
89 Correct 9 ms 8940 KB ok, no valid answer
90 Correct 10 ms 8940 KB ok, no valid answer
91 Correct 9 ms 8940 KB ok, no valid answer
92 Correct 10 ms 8940 KB ok, no valid answer
93 Correct 9 ms 8940 KB ok, no valid answer
94 Correct 207 ms 20904 KB ok, correct split
95 Correct 221 ms 25576 KB ok, correct split
96 Correct 262 ms 24200 KB ok, correct split
97 Correct 47 ms 13164 KB ok, correct split
98 Correct 46 ms 13292 KB ok, correct split
99 Correct 67 ms 15468 KB ok, correct split
100 Correct 227 ms 23424 KB ok, correct split
101 Correct 194 ms 22268 KB ok, correct split
102 Correct 200 ms 23008 KB ok, correct split
103 Correct 198 ms 22752 KB ok, correct split
104 Correct 163 ms 23896 KB ok, correct split
105 Correct 95 ms 15604 KB ok, correct split
106 Correct 156 ms 23380 KB ok, correct split
107 Correct 151 ms 19768 KB ok, correct split
108 Correct 158 ms 19760 KB ok, correct split
109 Correct 242 ms 22908 KB ok, correct split
110 Correct 260 ms 25440 KB ok, correct split
111 Correct 263 ms 25440 KB ok, correct split
112 Correct 278 ms 25824 KB ok, correct split
113 Correct 299 ms 25824 KB ok, correct split
114 Correct 23 ms 10476 KB ok, correct split
115 Correct 22 ms 10348 KB ok, correct split
116 Correct 207 ms 23008 KB ok, correct split
117 Correct 206 ms 22880 KB ok, correct split
118 Correct 158 ms 19484 KB ok, correct split
119 Correct 211 ms 19688 KB ok, correct split
120 Correct 199 ms 23396 KB ok, correct split
121 Correct 183 ms 18540 KB ok, no valid answer
122 Correct 150 ms 18860 KB ok, no valid answer
123 Correct 227 ms 22452 KB ok, no valid answer
124 Correct 229 ms 22380 KB ok, no valid answer
125 Correct 143 ms 20572 KB ok, no valid answer
126 Correct 92 ms 18268 KB ok, no valid answer
127 Correct 177 ms 21468 KB ok, no valid answer