oj.uz

Submission #796257

# Submission time Handle Problem Language Result Execution time Memory
796257 2023-07-28T08:25:07 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
37 / 100
 469 ms 62948 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

    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);
        assert(x!=y);
        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;

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

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;
    }
};

bool used[400002];
bool chk[400002];
ll yp[400002], yc[400002];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    for(int i=1; i<=m; i++){
        int x, y;
        cin >> 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<=m; i++) vec.push_back(make_pair(max(arr[ex[i]], arr[ey[i]]), i));
    sort(vec.begin(), vec.end());
    for(int i=0; i<m; i++){
        if(dsu.find(ex[vec[i].second]) == dsu.find(ey[vec[i].second])) continue;
        dsu.merge(ex[vec[i].second], ey[vec[i].second]);
        link[ex[vec[i].second]].push_back(ey[vec[i].second]);
        link[ey[vec[i].second]].push_back(ex[vec[i].second]);
    }

    dsu.init(n);

    vec.clear();
//    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(dat pr: reqVec){
            int y = pr.y; ll w = pr.cost, p = pr.profit;
            if(chk[dsu.find(y)]){
                assert(-w+p <= -yc[dsu.find(y)]+yp[dsu.find(y)]);
                continue;
            }
            chk[dsu.find(y)] = 1, yp[dsu.find(y)] = p, yc[dsu.find(y)] = w;
            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;
        }
        for(auto [y, w, p]: reqVec){
            if(dsu.find(x) == dsu.find(y)) continue;
            dsu.merge(x, y);
        }
        dsu.add(x, allAdd);
    }

    cout << ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 111 ms 47144 KB Output is correct
3 Correct 114 ms 47252 KB Output is correct
4 Correct 138 ms 50716 KB Output is correct
5 Correct 138 ms 50616 KB Output is correct
6 Correct 145 ms 50724 KB Output is correct
7 Correct 144 ms 50716 KB Output is correct
8 Correct 10 ms 19136 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 111 ms 47144 KB Output is correct
3 Correct 114 ms 47252 KB Output is correct
4 Correct 138 ms 50716 KB Output is correct
5 Correct 138 ms 50616 KB Output is correct
6 Correct 145 ms 50724 KB Output is correct
7 Correct 144 ms 50716 KB Output is correct
8 Correct 10 ms 19136 KB Output is correct
9 Correct 9 ms 19156 KB Output is correct
10 Correct 322 ms 60044 KB Output is correct
11 Correct 122 ms 47184 KB Output is correct
12 Correct 134 ms 47232 KB Output is correct
13 Correct 129 ms 47536 KB Output is correct
14 Correct 331 ms 59312 KB Output is correct
15 Correct 315 ms 59952 KB Output is correct
16 Correct 358 ms 60036 KB Output is correct
17 Correct 351 ms 59712 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 111 ms 47144 KB Output is correct
3 Correct 114 ms 47252 KB Output is correct
4 Correct 138 ms 50716 KB Output is correct
5 Correct 138 ms 50616 KB Output is correct
6 Correct 145 ms 50724 KB Output is correct
7 Correct 144 ms 50716 KB Output is correct
8 Correct 10 ms 19136 KB Output is correct
9 Correct 9 ms 19156 KB Output is correct
10 Correct 322 ms 60044 KB Output is correct
11 Correct 122 ms 47184 KB Output is correct
12 Correct 134 ms 47232 KB Output is correct
13 Correct 129 ms 47536 KB Output is correct
14 Correct 331 ms 59312 KB Output is correct
15 Correct 315 ms 59952 KB Output is correct
16 Correct 358 ms 60036 KB Output is correct
17 Correct 351 ms 59712 KB Output is correct
18 Correct 10 ms 19156 KB Output is correct
19 Correct 408 ms 60628 KB Output is correct
20 Correct 390 ms 60400 KB Output is correct
21 Correct 417 ms 57544 KB Output is correct
22 Correct 469 ms 54836 KB Output is correct
23 Correct 332 ms 55396 KB Output is correct
24 Correct 361 ms 54172 KB Output is correct
25 Correct 328 ms 56304 KB Output is correct
26 Correct 283 ms 61728 KB Output is correct
27 Correct 253 ms 62092 KB Output is correct
28 Correct 406 ms 58696 KB Output is correct
29 Correct 374 ms 57248 KB Output is correct
30 Correct 345 ms 56564 KB Output is correct
31 Correct 253 ms 61616 KB Output is correct
32 Correct 366 ms 52960 KB Output is correct
33 Correct 385 ms 61556 KB Output is correct
34 Correct 376 ms 56240 KB Output is correct
35 Correct 312 ms 55224 KB Output is correct
36 Correct 246 ms 53344 KB Output is correct
37 Correct 241 ms 53348 KB Output is correct
38 Correct 325 ms 62948 KB Output is correct
39 Correct 282 ms 49520 KB Output is correct
40 Correct 353 ms 60424 KB Output is correct
41 Correct 332 ms 47176 KB Output is correct
42 Correct 345 ms 47156 KB Output is correct
43 Correct 327 ms 54408 KB Output is correct
44 Correct 390 ms 53928 KB Output is correct
45 Correct 403 ms 54800 KB Output is correct
46 Correct 361 ms 54028 KB Output is correct
47 Correct 363 ms 54396 KB Output is correct
48 Correct 408 ms 54396 KB Output is correct
49 Correct 405 ms 48416 KB Output is correct
50 Correct 398 ms 60140 KB Output is correct
51 Correct 300 ms 55064 KB Output is correct
52 Correct 298 ms 54736 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 111 ms 47144 KB Output is correct
3 Correct 114 ms 47252 KB Output is correct
4 Correct 138 ms 50716 KB Output is correct
5 Correct 138 ms 50616 KB Output is correct
6 Correct 145 ms 50724 KB Output is correct
7 Correct 144 ms 50716 KB Output is correct
8 Correct 10 ms 19136 KB Output is correct
9 Correct 9 ms 19156 KB Output is correct
10 Correct 322 ms 60044 KB Output is correct
11 Correct 122 ms 47184 KB Output is correct
12 Correct 134 ms 47232 KB Output is correct
13 Correct 129 ms 47536 KB Output is correct
14 Correct 331 ms 59312 KB Output is correct
15 Correct 315 ms 59952 KB Output is correct
16 Correct 358 ms 60036 KB Output is correct
17 Correct 351 ms 59712 KB Output is correct
18 Correct 10 ms 19156 KB Output is correct
19 Correct 408 ms 60628 KB Output is correct
20 Correct 390 ms 60400 KB Output is correct
21 Correct 417 ms 57544 KB Output is correct
22 Correct 469 ms 54836 KB Output is correct
23 Correct 332 ms 55396 KB Output is correct
24 Correct 361 ms 54172 KB Output is correct
25 Correct 328 ms 56304 KB Output is correct
26 Correct 283 ms 61728 KB Output is correct
27 Correct 253 ms 62092 KB Output is correct
28 Correct 406 ms 58696 KB Output is correct
29 Correct 374 ms 57248 KB Output is correct
30 Correct 345 ms 56564 KB Output is correct
31 Correct 253 ms 61616 KB Output is correct
32 Correct 366 ms 52960 KB Output is correct
33 Correct 385 ms 61556 KB Output is correct
34 Correct 376 ms 56240 KB Output is correct
35 Correct 312 ms 55224 KB Output is correct
36 Correct 246 ms 53344 KB Output is correct
37 Correct 241 ms 53348 KB Output is correct
38 Correct 325 ms 62948 KB Output is correct
39 Correct 282 ms 49520 KB Output is correct
40 Correct 353 ms 60424 KB Output is correct
41 Correct 332 ms 47176 KB Output is correct
42 Correct 345 ms 47156 KB Output is correct
43 Correct 327 ms 54408 KB Output is correct
44 Correct 390 ms 53928 KB Output is correct
45 Correct 403 ms 54800 KB Output is correct
46 Correct 361 ms 54028 KB Output is correct
47 Correct 363 ms 54396 KB Output is correct
48 Correct 408 ms 54396 KB Output is correct
49 Correct 405 ms 48416 KB Output is correct
50 Correct 398 ms 60140 KB Output is correct
51 Correct 300 ms 55064 KB Output is correct
52 Correct 298 ms 54736 KB Output is correct
53 Correct 9 ms 19084 KB Output is correct
54 Incorrect 451 ms 59084 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Incorrect 10 ms 19100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Incorrect 10 ms 19100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 111 ms 47144 KB Output is correct
3 Correct 114 ms 47252 KB Output is correct
4 Correct 138 ms 50716 KB Output is correct
5 Correct 138 ms 50616 KB Output is correct
6 Correct 145 ms 50724 KB Output is correct
7 Correct 144 ms 50716 KB Output is correct
8 Correct 10 ms 19136 KB Output is correct
9 Correct 9 ms 19156 KB Output is correct
10 Correct 322 ms 60044 KB Output is correct
11 Correct 122 ms 47184 KB Output is correct
12 Correct 134 ms 47232 KB Output is correct
13 Correct 129 ms 47536 KB Output is correct
14 Correct 331 ms 59312 KB Output is correct
15 Correct 315 ms 59952 KB Output is correct
16 Correct 358 ms 60036 KB Output is correct
17 Correct 351 ms 59712 KB Output is correct
18 Correct 10 ms 19156 KB Output is correct
19 Correct 408 ms 60628 KB Output is correct
20 Correct 390 ms 60400 KB Output is correct
21 Correct 417 ms 57544 KB Output is correct
22 Correct 469 ms 54836 KB Output is correct
23 Correct 332 ms 55396 KB Output is correct
24 Correct 361 ms 54172 KB Output is correct
25 Correct 328 ms 56304 KB Output is correct
26 Correct 283 ms 61728 KB Output is correct
27 Correct 253 ms 62092 KB Output is correct
28 Correct 406 ms 58696 KB Output is correct
29 Correct 374 ms 57248 KB Output is correct
30 Correct 345 ms 56564 KB Output is correct
31 Correct 253 ms 61616 KB Output is correct
32 Correct 366 ms 52960 KB Output is correct
33 Correct 385 ms 61556 KB Output is correct
34 Correct 376 ms 56240 KB Output is correct
35 Correct 312 ms 55224 KB Output is correct
36 Correct 246 ms 53344 KB Output is correct
37 Correct 241 ms 53348 KB Output is correct
38 Correct 325 ms 62948 KB Output is correct
39 Correct 282 ms 49520 KB Output is correct
40 Correct 353 ms 60424 KB Output is correct
41 Correct 332 ms 47176 KB Output is correct
42 Correct 345 ms 47156 KB Output is correct
43 Correct 327 ms 54408 KB Output is correct
44 Correct 390 ms 53928 KB Output is correct
45 Correct 403 ms 54800 KB Output is correct
46 Correct 361 ms 54028 KB Output is correct
47 Correct 363 ms 54396 KB Output is correct
48 Correct 408 ms 54396 KB Output is correct
49 Correct 405 ms 48416 KB Output is correct
50 Correct 398 ms 60140 KB Output is correct
51 Correct 300 ms 55064 KB Output is correct
52 Correct 298 ms 54736 KB Output is correct
53 Correct 9 ms 19084 KB Output is correct
54 Incorrect 451 ms 59084 KB Output isn't correct
55 Halted 0 ms 0 KB -