oj.uz

Submission #796263

# Submission time Handle Problem Language Result Execution time Memory
796263 2023-07-28T08:34:04 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
37 / 100
 273 ms 57600 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];
int 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<=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)] == x){
                assert(-w+p <= -yc[dsu.find(y)]+yp[dsu.find(y)]);
                continue;
            }
            chk[dsu.find(y)] = x, 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(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 19164 KB Output is correct
2 Correct 89 ms 45336 KB Output is correct
3 Correct 88 ms 45388 KB Output is correct
4 Correct 101 ms 49460 KB Output is correct
5 Correct 103 ms 49492 KB Output is correct
6 Correct 102 ms 49440 KB Output is correct
7 Correct 103 ms 49412 KB Output is correct
8 Correct 11 ms 19124 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19164 KB Output is correct
2 Correct 89 ms 45336 KB Output is correct
3 Correct 88 ms 45388 KB Output is correct
4 Correct 101 ms 49460 KB Output is correct
5 Correct 103 ms 49492 KB Output is correct
6 Correct 102 ms 49440 KB Output is correct
7 Correct 103 ms 49412 KB Output is correct
8 Correct 11 ms 19124 KB Output is correct
9 Correct 10 ms 19168 KB Output is correct
10 Correct 212 ms 55660 KB Output is correct
11 Correct 99 ms 45432 KB Output is correct
12 Correct 95 ms 45328 KB Output is correct
13 Correct 91 ms 45732 KB Output is correct
14 Correct 211 ms 55392 KB Output is correct
15 Correct 213 ms 56196 KB Output is correct
16 Correct 233 ms 55832 KB Output is correct
17 Correct 208 ms 55612 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19164 KB Output is correct
2 Correct 89 ms 45336 KB Output is correct
3 Correct 88 ms 45388 KB Output is correct
4 Correct 101 ms 49460 KB Output is correct
5 Correct 103 ms 49492 KB Output is correct
6 Correct 102 ms 49440 KB Output is correct
7 Correct 103 ms 49412 KB Output is correct
8 Correct 11 ms 19124 KB Output is correct
9 Correct 10 ms 19168 KB Output is correct
10 Correct 212 ms 55660 KB Output is correct
11 Correct 99 ms 45432 KB Output is correct
12 Correct 95 ms 45328 KB Output is correct
13 Correct 91 ms 45732 KB Output is correct
14 Correct 211 ms 55392 KB Output is correct
15 Correct 213 ms 56196 KB Output is correct
16 Correct 233 ms 55832 KB Output is correct
17 Correct 208 ms 55612 KB Output is correct
18 Correct 10 ms 19172 KB Output is correct
19 Correct 254 ms 55228 KB Output is correct
20 Correct 273 ms 54852 KB Output is correct
21 Correct 270 ms 53180 KB Output is correct
22 Correct 238 ms 51376 KB Output is correct
23 Correct 228 ms 52292 KB Output is correct
24 Correct 201 ms 51296 KB Output is correct
25 Correct 203 ms 51488 KB Output is correct
26 Correct 172 ms 53800 KB Output is correct
27 Correct 174 ms 55672 KB Output is correct
28 Correct 238 ms 54964 KB Output is correct
29 Correct 244 ms 53748 KB Output is correct
30 Correct 238 ms 51360 KB Output is correct
31 Correct 165 ms 55600 KB Output is correct
32 Correct 212 ms 49744 KB Output is correct
33 Correct 231 ms 57600 KB Output is correct
34 Correct 208 ms 51860 KB Output is correct
35 Correct 184 ms 51548 KB Output is correct
36 Correct 157 ms 50368 KB Output is correct
37 Correct 153 ms 50464 KB Output is correct
38 Correct 238 ms 54192 KB Output is correct
39 Correct 174 ms 46616 KB Output is correct
40 Correct 205 ms 53932 KB Output is correct
41 Correct 210 ms 45340 KB Output is correct
42 Correct 205 ms 45472 KB Output is correct
43 Correct 214 ms 50472 KB Output is correct
44 Correct 260 ms 50500 KB Output is correct
45 Correct 217 ms 50960 KB Output is correct
46 Correct 222 ms 50468 KB Output is correct
47 Correct 253 ms 50920 KB Output is correct
48 Correct 236 ms 50840 KB Output is correct
49 Correct 227 ms 45560 KB Output is correct
50 Correct 252 ms 54372 KB Output is correct
51 Correct 180 ms 51140 KB Output is correct
52 Correct 186 ms 50576 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19164 KB Output is correct
2 Correct 89 ms 45336 KB Output is correct
3 Correct 88 ms 45388 KB Output is correct
4 Correct 101 ms 49460 KB Output is correct
5 Correct 103 ms 49492 KB Output is correct
6 Correct 102 ms 49440 KB Output is correct
7 Correct 103 ms 49412 KB Output is correct
8 Correct 11 ms 19124 KB Output is correct
9 Correct 10 ms 19168 KB Output is correct
10 Correct 212 ms 55660 KB Output is correct
11 Correct 99 ms 45432 KB Output is correct
12 Correct 95 ms 45328 KB Output is correct
13 Correct 91 ms 45732 KB Output is correct
14 Correct 211 ms 55392 KB Output is correct
15 Correct 213 ms 56196 KB Output is correct
16 Correct 233 ms 55832 KB Output is correct
17 Correct 208 ms 55612 KB Output is correct
18 Correct 10 ms 19172 KB Output is correct
19 Correct 254 ms 55228 KB Output is correct
20 Correct 273 ms 54852 KB Output is correct
21 Correct 270 ms 53180 KB Output is correct
22 Correct 238 ms 51376 KB Output is correct
23 Correct 228 ms 52292 KB Output is correct
24 Correct 201 ms 51296 KB Output is correct
25 Correct 203 ms 51488 KB Output is correct
26 Correct 172 ms 53800 KB Output is correct
27 Correct 174 ms 55672 KB Output is correct
28 Correct 238 ms 54964 KB Output is correct
29 Correct 244 ms 53748 KB Output is correct
30 Correct 238 ms 51360 KB Output is correct
31 Correct 165 ms 55600 KB Output is correct
32 Correct 212 ms 49744 KB Output is correct
33 Correct 231 ms 57600 KB Output is correct
34 Correct 208 ms 51860 KB Output is correct
35 Correct 184 ms 51548 KB Output is correct
36 Correct 157 ms 50368 KB Output is correct
37 Correct 153 ms 50464 KB Output is correct
38 Correct 238 ms 54192 KB Output is correct
39 Correct 174 ms 46616 KB Output is correct
40 Correct 205 ms 53932 KB Output is correct
41 Correct 210 ms 45340 KB Output is correct
42 Correct 205 ms 45472 KB Output is correct
43 Correct 214 ms 50472 KB Output is correct
44 Correct 260 ms 50500 KB Output is correct
45 Correct 217 ms 50960 KB Output is correct
46 Correct 222 ms 50468 KB Output is correct
47 Correct 253 ms 50920 KB Output is correct
48 Correct 236 ms 50840 KB Output is correct
49 Correct 227 ms 45560 KB Output is correct
50 Correct 252 ms 54372 KB Output is correct
51 Correct 180 ms 51140 KB Output is correct
52 Correct 186 ms 50576 KB Output is correct
53 Correct 11 ms 19284 KB Output is correct
54 Incorrect 240 ms 54436 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Incorrect 10 ms 19084 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 19164 KB Output is correct
2 Correct 89 ms 45336 KB Output is correct
3 Correct 88 ms 45388 KB Output is correct
4 Correct 101 ms 49460 KB Output is correct
5 Correct 103 ms 49492 KB Output is correct
6 Correct 102 ms 49440 KB Output is correct
7 Correct 103 ms 49412 KB Output is correct
8 Correct 11 ms 19124 KB Output is correct
9 Correct 10 ms 19168 KB Output is correct
10 Correct 212 ms 55660 KB Output is correct
11 Correct 99 ms 45432 KB Output is correct
12 Correct 95 ms 45328 KB Output is correct
13 Correct 91 ms 45732 KB Output is correct
14 Correct 211 ms 55392 KB Output is correct
15 Correct 213 ms 56196 KB Output is correct
16 Correct 233 ms 55832 KB Output is correct
17 Correct 208 ms 55612 KB Output is correct
18 Correct 10 ms 19172 KB Output is correct
19 Correct 254 ms 55228 KB Output is correct
20 Correct 273 ms 54852 KB Output is correct
21 Correct 270 ms 53180 KB Output is correct
22 Correct 238 ms 51376 KB Output is correct
23 Correct 228 ms 52292 KB Output is correct
24 Correct 201 ms 51296 KB Output is correct
25 Correct 203 ms 51488 KB Output is correct
26 Correct 172 ms 53800 KB Output is correct
27 Correct 174 ms 55672 KB Output is correct
28 Correct 238 ms 54964 KB Output is correct
29 Correct 244 ms 53748 KB Output is correct
30 Correct 238 ms 51360 KB Output is correct
31 Correct 165 ms 55600 KB Output is correct
32 Correct 212 ms 49744 KB Output is correct
33 Correct 231 ms 57600 KB Output is correct
34 Correct 208 ms 51860 KB Output is correct
35 Correct 184 ms 51548 KB Output is correct
36 Correct 157 ms 50368 KB Output is correct
37 Correct 153 ms 50464 KB Output is correct
38 Correct 238 ms 54192 KB Output is correct
39 Correct 174 ms 46616 KB Output is correct
40 Correct 205 ms 53932 KB Output is correct
41 Correct 210 ms 45340 KB Output is correct
42 Correct 205 ms 45472 KB Output is correct
43 Correct 214 ms 50472 KB Output is correct
44 Correct 260 ms 50500 KB Output is correct
45 Correct 217 ms 50960 KB Output is correct
46 Correct 222 ms 50468 KB Output is correct
47 Correct 253 ms 50920 KB Output is correct
48 Correct 236 ms 50840 KB Output is correct
49 Correct 227 ms 45560 KB Output is correct
50 Correct 252 ms 54372 KB Output is correct
51 Correct 180 ms 51140 KB Output is correct
52 Correct 186 ms 50576 KB Output is correct
53 Correct 11 ms 19284 KB Output is correct
54 Incorrect 240 ms 54436 KB Output isn't correct
55 Halted 0 ms 0 KB -