oj.uz

Submission #796203

# Submission time Handle Problem Language Result Execution time Memory
796203 2023-07-28T07:50:40 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
37 / 100
 288 ms 60796 KB 
#include <bits/stdc++.h>
#define int ll

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];
ll yp[200002], yc[200002];

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)]){
                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;
            dsu.merge(x, y);
        }
        dsu.add(x, allAdd);
    }

    cout << ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 84 ms 38532 KB Output is correct
3 Correct 87 ms 38532 KB Output is correct
4 Correct 101 ms 42692 KB Output is correct
5 Correct 100 ms 42592 KB Output is correct
6 Correct 98 ms 42508 KB Output is correct
7 Correct 103 ms 42592 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 84 ms 38532 KB Output is correct
3 Correct 87 ms 38532 KB Output is correct
4 Correct 101 ms 42692 KB Output is correct
5 Correct 100 ms 42592 KB Output is correct
6 Correct 98 ms 42508 KB Output is correct
7 Correct 103 ms 42592 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 207 ms 54624 KB Output is correct
11 Correct 96 ms 38524 KB Output is correct
12 Correct 90 ms 38548 KB Output is correct
13 Correct 106 ms 38804 KB Output is correct
14 Correct 206 ms 54176 KB Output is correct
15 Correct 209 ms 55780 KB Output is correct
16 Correct 220 ms 54992 KB Output is correct
17 Correct 220 ms 54756 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 84 ms 38532 KB Output is correct
3 Correct 87 ms 38532 KB Output is correct
4 Correct 101 ms 42692 KB Output is correct
5 Correct 100 ms 42592 KB Output is correct
6 Correct 98 ms 42508 KB Output is correct
7 Correct 103 ms 42592 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 207 ms 54624 KB Output is correct
11 Correct 96 ms 38524 KB Output is correct
12 Correct 90 ms 38548 KB Output is correct
13 Correct 106 ms 38804 KB Output is correct
14 Correct 206 ms 54176 KB Output is correct
15 Correct 209 ms 55780 KB Output is correct
16 Correct 220 ms 54992 KB Output is correct
17 Correct 220 ms 54756 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 268 ms 54520 KB Output is correct
20 Correct 259 ms 53976 KB Output is correct
21 Correct 279 ms 50648 KB Output is correct
22 Correct 237 ms 46976 KB Output is correct
23 Correct 239 ms 47824 KB Output is correct
24 Correct 189 ms 45364 KB Output is correct
25 Correct 209 ms 45268 KB Output is correct
26 Correct 189 ms 46044 KB Output is correct
27 Correct 174 ms 47592 KB Output is correct
28 Correct 277 ms 53216 KB Output is correct
29 Correct 227 ms 50988 KB Output is correct
30 Correct 222 ms 45492 KB Output is correct
31 Correct 158 ms 47640 KB Output is correct
32 Correct 252 ms 43616 KB Output is correct
33 Correct 239 ms 60796 KB Output is correct
34 Correct 196 ms 47964 KB Output is correct
35 Correct 212 ms 46404 KB Output is correct
36 Correct 144 ms 44008 KB Output is correct
37 Correct 142 ms 43896 KB Output is correct
38 Correct 199 ms 51412 KB Output is correct
39 Correct 176 ms 39984 KB Output is correct
40 Correct 209 ms 49060 KB Output is correct
41 Correct 229 ms 38584 KB Output is correct
42 Correct 214 ms 38628 KB Output is correct
43 Correct 246 ms 45284 KB Output is correct
44 Correct 251 ms 45200 KB Output is correct
45 Correct 223 ms 46248 KB Output is correct
46 Correct 226 ms 45268 KB Output is correct
47 Correct 252 ms 45900 KB Output is correct
48 Correct 249 ms 46000 KB Output is correct
49 Correct 245 ms 39792 KB Output is correct
50 Correct 242 ms 53084 KB Output is correct
51 Correct 193 ms 46660 KB Output is correct
52 Correct 200 ms 45468 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 84 ms 38532 KB Output is correct
3 Correct 87 ms 38532 KB Output is correct
4 Correct 101 ms 42692 KB Output is correct
5 Correct 100 ms 42592 KB Output is correct
6 Correct 98 ms 42508 KB Output is correct
7 Correct 103 ms 42592 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 207 ms 54624 KB Output is correct
11 Correct 96 ms 38524 KB Output is correct
12 Correct 90 ms 38548 KB Output is correct
13 Correct 106 ms 38804 KB Output is correct
14 Correct 206 ms 54176 KB Output is correct
15 Correct 209 ms 55780 KB Output is correct
16 Correct 220 ms 54992 KB Output is correct
17 Correct 220 ms 54756 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 268 ms 54520 KB Output is correct
20 Correct 259 ms 53976 KB Output is correct
21 Correct 279 ms 50648 KB Output is correct
22 Correct 237 ms 46976 KB Output is correct
23 Correct 239 ms 47824 KB Output is correct
24 Correct 189 ms 45364 KB Output is correct
25 Correct 209 ms 45268 KB Output is correct
26 Correct 189 ms 46044 KB Output is correct
27 Correct 174 ms 47592 KB Output is correct
28 Correct 277 ms 53216 KB Output is correct
29 Correct 227 ms 50988 KB Output is correct
30 Correct 222 ms 45492 KB Output is correct
31 Correct 158 ms 47640 KB Output is correct
32 Correct 252 ms 43616 KB Output is correct
33 Correct 239 ms 60796 KB Output is correct
34 Correct 196 ms 47964 KB Output is correct
35 Correct 212 ms 46404 KB Output is correct
36 Correct 144 ms 44008 KB Output is correct
37 Correct 142 ms 43896 KB Output is correct
38 Correct 199 ms 51412 KB Output is correct
39 Correct 176 ms 39984 KB Output is correct
40 Correct 209 ms 49060 KB Output is correct
41 Correct 229 ms 38584 KB Output is correct
42 Correct 214 ms 38628 KB Output is correct
43 Correct 246 ms 45284 KB Output is correct
44 Correct 251 ms 45200 KB Output is correct
45 Correct 223 ms 46248 KB Output is correct
46 Correct 226 ms 45268 KB Output is correct
47 Correct 252 ms 45900 KB Output is correct
48 Correct 249 ms 46000 KB Output is correct
49 Correct 245 ms 39792 KB Output is correct
50 Correct 242 ms 53084 KB Output is correct
51 Correct 193 ms 46660 KB Output is correct
52 Correct 200 ms 45468 KB Output is correct
53 Correct 5 ms 9684 KB Output is correct
54 Incorrect 288 ms 52828 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 5 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 5 ms 9684 KB Output is correct
2 Incorrect 5 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 6 ms 9684 KB Output is correct
2 Correct 84 ms 38532 KB Output is correct
3 Correct 87 ms 38532 KB Output is correct
4 Correct 101 ms 42692 KB Output is correct
5 Correct 100 ms 42592 KB Output is correct
6 Correct 98 ms 42508 KB Output is correct
7 Correct 103 ms 42592 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 207 ms 54624 KB Output is correct
11 Correct 96 ms 38524 KB Output is correct
12 Correct 90 ms 38548 KB Output is correct
13 Correct 106 ms 38804 KB Output is correct
14 Correct 206 ms 54176 KB Output is correct
15 Correct 209 ms 55780 KB Output is correct
16 Correct 220 ms 54992 KB Output is correct
17 Correct 220 ms 54756 KB Output is correct
18 Correct 5 ms 9676 KB Output is correct
19 Correct 268 ms 54520 KB Output is correct
20 Correct 259 ms 53976 KB Output is correct
21 Correct 279 ms 50648 KB Output is correct
22 Correct 237 ms 46976 KB Output is correct
23 Correct 239 ms 47824 KB Output is correct
24 Correct 189 ms 45364 KB Output is correct
25 Correct 209 ms 45268 KB Output is correct
26 Correct 189 ms 46044 KB Output is correct
27 Correct 174 ms 47592 KB Output is correct
28 Correct 277 ms 53216 KB Output is correct
29 Correct 227 ms 50988 KB Output is correct
30 Correct 222 ms 45492 KB Output is correct
31 Correct 158 ms 47640 KB Output is correct
32 Correct 252 ms 43616 KB Output is correct
33 Correct 239 ms 60796 KB Output is correct
34 Correct 196 ms 47964 KB Output is correct
35 Correct 212 ms 46404 KB Output is correct
36 Correct 144 ms 44008 KB Output is correct
37 Correct 142 ms 43896 KB Output is correct
38 Correct 199 ms 51412 KB Output is correct
39 Correct 176 ms 39984 KB Output is correct
40 Correct 209 ms 49060 KB Output is correct
41 Correct 229 ms 38584 KB Output is correct
42 Correct 214 ms 38628 KB Output is correct
43 Correct 246 ms 45284 KB Output is correct
44 Correct 251 ms 45200 KB Output is correct
45 Correct 223 ms 46248 KB Output is correct
46 Correct 226 ms 45268 KB Output is correct
47 Correct 252 ms 45900 KB Output is correct
48 Correct 249 ms 46000 KB Output is correct
49 Correct 245 ms 39792 KB Output is correct
50 Correct 242 ms 53084 KB Output is correct
51 Correct 193 ms 46660 KB Output is correct
52 Correct 200 ms 45468 KB Output is correct
53 Correct 5 ms 9684 KB Output is correct
54 Incorrect 288 ms 52828 KB Output isn't correct
55 Halted 0 ms 0 KB -