oj.uz

Submission #796152

# Submission time Handle Problem Language Result Execution time Memory
796152 2023-07-28T07:09:02 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
37 / 100
 284 ms 44340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[200002];
    ll groupAdd[200002], oneAdd[200002];
    vector<int> vec[200002];

    void init(int n){
        for(int i=1; i<=n; i++){
            par[i] = i;
            groupAdd[i] = oneAdd[i] = 0;
            vec[i].push_back(i);
        }
    }

    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x==y) return;
        if(vec[x].size() < vec[y].size()) swap(x, y);
        for(int p: vec[y]){
            vec[x].push_back(p);
            oneAdd[p] += groupAdd[y] - groupAdd[x];
        }
        groupAdd[y] = 0;
        par[y] = x;
        vec[y].clear();
    }

    inline ll query(int x){
        return oneAdd[x] + groupAdd[find(x)];
    }

    inline void add(int x, ll y){
        groupAdd[find(x)] += y;
    }
} dsu;

struct dat{
    int y; ll cost, profit;
    dat(){}
    dat(int y, ll cost, ll profit): y(y), cost(cost), profit(profit){}
    bool operator<(const dat &r)const{
        if(cost != r.cost) return cost < r.cost;
        return profit > r.profit;
    }
};

int n, m, q;
ll arr[200002], ex[400002], ey[400002];
vector<int> link[200002];
ll ans;

bool used[200002];
bool chk[200002];

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
    }
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        ex[i] = x, ey[i] = y;
        link[x].push_back(y);
        link[y].push_back(x);
    }

    dsu.init(n);

    vector<pair<ll, int> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(arr[i], i));
    sort(vec.begin(), vec.end());

    for(auto [v, x]: vec){
        vector<dat> reqVec; /// � �������� �������� �󸶳� �ʿ������� ����� ��
        used[x] = 1;
        for(auto y: link[x]){
            if(!used[y]) continue;
            ll w = arr[x] - dsu.query(y);
            reqVec.push_back(dat(y, max(arr[y], w), w > arr[y] ? 0 : arr[y] - w));
        }
        sort(reqVec.begin(), reqVec.end());

        ll allAdd = 0;
        for(auto [y, w, p]: reqVec){
            if(chk[dsu.find(y)]) continue;
            chk[dsu.find(y)] = 1;
            ans += w;
            if(w > arr[y]) dsu.add(y, w-arr[y]); /// y �ʿ� �̵��� �ִ�
            else{
                ll tmp = p;
                allAdd += tmp;
                dsu.add(y, -tmp);
            }
        }
        for(auto [y, w, p]: reqVec){
            if(!chk[dsu.find(y)]) continue;
            chk[dsu.find(y)] = 0;
            dsu.merge(x, y);
        }
        dsu.add(x, allAdd);
    }

    printf("%lld", ans);
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
guard.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 96 ms 35948 KB Output is correct
3 Correct 92 ms 35968 KB Output is correct
4 Correct 104 ms 36292 KB Output is correct
5 Correct 103 ms 36284 KB Output is correct
6 Correct 103 ms 36236 KB Output is correct
7 Correct 109 ms 36304 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 96 ms 35948 KB Output is correct
3 Correct 92 ms 35968 KB Output is correct
4 Correct 104 ms 36292 KB Output is correct
5 Correct 103 ms 36284 KB Output is correct
6 Correct 103 ms 36236 KB Output is correct
7 Correct 109 ms 36304 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 189 ms 42436 KB Output is correct
11 Correct 97 ms 35968 KB Output is correct
12 Correct 107 ms 35864 KB Output is correct
13 Correct 96 ms 36032 KB Output is correct
14 Correct 195 ms 42212 KB Output is correct
15 Correct 187 ms 43064 KB Output is correct
16 Correct 187 ms 42572 KB Output is correct
17 Correct 195 ms 42512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 96 ms 35948 KB Output is correct
3 Correct 92 ms 35968 KB Output is correct
4 Correct 104 ms 36292 KB Output is correct
5 Correct 103 ms 36284 KB Output is correct
6 Correct 103 ms 36236 KB Output is correct
7 Correct 109 ms 36304 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 189 ms 42436 KB Output is correct
11 Correct 97 ms 35968 KB Output is correct
12 Correct 107 ms 35864 KB Output is correct
13 Correct 96 ms 36032 KB Output is correct
14 Correct 195 ms 42212 KB Output is correct
15 Correct 187 ms 43064 KB Output is correct
16 Correct 187 ms 42572 KB Output is correct
17 Correct 195 ms 42512 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 235 ms 42264 KB Output is correct
20 Correct 251 ms 41644 KB Output is correct
21 Correct 225 ms 40080 KB Output is correct
22 Correct 214 ms 38184 KB Output is correct
23 Correct 193 ms 39152 KB Output is correct
24 Correct 204 ms 38120 KB Output is correct
25 Correct 191 ms 38320 KB Output is correct
26 Correct 190 ms 40588 KB Output is correct
27 Correct 167 ms 44156 KB Output is correct
28 Correct 284 ms 41824 KB Output is correct
29 Correct 205 ms 40616 KB Output is correct
30 Correct 195 ms 38180 KB Output is correct
31 Correct 153 ms 44080 KB Output is correct
32 Correct 232 ms 36540 KB Output is correct
33 Correct 202 ms 44340 KB Output is correct
34 Correct 176 ms 38700 KB Output is correct
35 Correct 169 ms 38316 KB Output is correct
36 Correct 146 ms 37240 KB Output is correct
37 Correct 164 ms 37236 KB Output is correct
38 Correct 199 ms 40996 KB Output is correct
39 Correct 176 ms 36372 KB Output is correct
40 Correct 188 ms 40828 KB Output is correct
41 Correct 255 ms 35864 KB Output is correct
42 Correct 204 ms 35924 KB Output is correct
43 Correct 204 ms 37264 KB Output is correct
44 Correct 214 ms 37252 KB Output is correct
45 Correct 190 ms 37804 KB Output is correct
46 Correct 196 ms 37236 KB Output is correct
47 Correct 220 ms 37620 KB Output is correct
48 Correct 216 ms 37604 KB Output is correct
49 Correct 217 ms 36092 KB Output is correct
50 Correct 223 ms 41216 KB Output is correct
51 Correct 204 ms 38016 KB Output is correct
52 Correct 159 ms 37336 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 96 ms 35948 KB Output is correct
3 Correct 92 ms 35968 KB Output is correct
4 Correct 104 ms 36292 KB Output is correct
5 Correct 103 ms 36284 KB Output is correct
6 Correct 103 ms 36236 KB Output is correct
7 Correct 109 ms 36304 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 189 ms 42436 KB Output is correct
11 Correct 97 ms 35968 KB Output is correct
12 Correct 107 ms 35864 KB Output is correct
13 Correct 96 ms 36032 KB Output is correct
14 Correct 195 ms 42212 KB Output is correct
15 Correct 187 ms 43064 KB Output is correct
16 Correct 187 ms 42572 KB Output is correct
17 Correct 195 ms 42512 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 235 ms 42264 KB Output is correct
20 Correct 251 ms 41644 KB Output is correct
21 Correct 225 ms 40080 KB Output is correct
22 Correct 214 ms 38184 KB Output is correct
23 Correct 193 ms 39152 KB Output is correct
24 Correct 204 ms 38120 KB Output is correct
25 Correct 191 ms 38320 KB Output is correct
26 Correct 190 ms 40588 KB Output is correct
27 Correct 167 ms 44156 KB Output is correct
28 Correct 284 ms 41824 KB Output is correct
29 Correct 205 ms 40616 KB Output is correct
30 Correct 195 ms 38180 KB Output is correct
31 Correct 153 ms 44080 KB Output is correct
32 Correct 232 ms 36540 KB Output is correct
33 Correct 202 ms 44340 KB Output is correct
34 Correct 176 ms 38700 KB Output is correct
35 Correct 169 ms 38316 KB Output is correct
36 Correct 146 ms 37240 KB Output is correct
37 Correct 164 ms 37236 KB Output is correct
38 Correct 199 ms 40996 KB Output is correct
39 Correct 176 ms 36372 KB Output is correct
40 Correct 188 ms 40828 KB Output is correct
41 Correct 255 ms 35864 KB Output is correct
42 Correct 204 ms 35924 KB Output is correct
43 Correct 204 ms 37264 KB Output is correct
44 Correct 214 ms 37252 KB Output is correct
45 Correct 190 ms 37804 KB Output is correct
46 Correct 196 ms 37236 KB Output is correct
47 Correct 220 ms 37620 KB Output is correct
48 Correct 216 ms 37604 KB Output is correct
49 Correct 217 ms 36092 KB Output is correct
50 Correct 223 ms 41216 KB Output is correct
51 Correct 204 ms 38016 KB Output is correct
52 Correct 159 ms 37336 KB Output is correct
53 Correct 4 ms 9684 KB Output is correct
54 Incorrect 250 ms 41248 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Incorrect 4 ms 9684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Incorrect 4 ms 9684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 96 ms 35948 KB Output is correct
3 Correct 92 ms 35968 KB Output is correct
4 Correct 104 ms 36292 KB Output is correct
5 Correct 103 ms 36284 KB Output is correct
6 Correct 103 ms 36236 KB Output is correct
7 Correct 109 ms 36304 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 189 ms 42436 KB Output is correct
11 Correct 97 ms 35968 KB Output is correct
12 Correct 107 ms 35864 KB Output is correct
13 Correct 96 ms 36032 KB Output is correct
14 Correct 195 ms 42212 KB Output is correct
15 Correct 187 ms 43064 KB Output is correct
16 Correct 187 ms 42572 KB Output is correct
17 Correct 195 ms 42512 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 235 ms 42264 KB Output is correct
20 Correct 251 ms 41644 KB Output is correct
21 Correct 225 ms 40080 KB Output is correct
22 Correct 214 ms 38184 KB Output is correct
23 Correct 193 ms 39152 KB Output is correct
24 Correct 204 ms 38120 KB Output is correct
25 Correct 191 ms 38320 KB Output is correct
26 Correct 190 ms 40588 KB Output is correct
27 Correct 167 ms 44156 KB Output is correct
28 Correct 284 ms 41824 KB Output is correct
29 Correct 205 ms 40616 KB Output is correct
30 Correct 195 ms 38180 KB Output is correct
31 Correct 153 ms 44080 KB Output is correct
32 Correct 232 ms 36540 KB Output is correct
33 Correct 202 ms 44340 KB Output is correct
34 Correct 176 ms 38700 KB Output is correct
35 Correct 169 ms 38316 KB Output is correct
36 Correct 146 ms 37240 KB Output is correct
37 Correct 164 ms 37236 KB Output is correct
38 Correct 199 ms 40996 KB Output is correct
39 Correct 176 ms 36372 KB Output is correct
40 Correct 188 ms 40828 KB Output is correct
41 Correct 255 ms 35864 KB Output is correct
42 Correct 204 ms 35924 KB Output is correct
43 Correct 204 ms 37264 KB Output is correct
44 Correct 214 ms 37252 KB Output is correct
45 Correct 190 ms 37804 KB Output is correct
46 Correct 196 ms 37236 KB Output is correct
47 Correct 220 ms 37620 KB Output is correct
48 Correct 216 ms 37604 KB Output is correct
49 Correct 217 ms 36092 KB Output is correct
50 Correct 223 ms 41216 KB Output is correct
51 Correct 204 ms 38016 KB Output is correct
52 Correct 159 ms 37336 KB Output is correct
53 Correct 4 ms 9684 KB Output is correct
54 Incorrect 250 ms 41248 KB Output isn't correct
55 Halted 0 ms 0 KB -