oj.uz

Submission #796197

# Submission time Handle Problem Language Result Execution time Memory
796197 2023-07-28T07:43:12 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
37 / 100
 308 ms 47504 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];
ll yp[200002], yc[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(dat pr: reqVec){
            int y = pr.y; ll w = pr.cost, p = pr.profit;
            if(chk[dsu.find(y)]){
                assert(-w+p >= -yc[y]+yp[y]);
                continue;
            }
            chk[dsu.find(y)] = 1, yp[y] = p, yc[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);
    }

    printf("%lld", ans);
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
guard.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         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 39000 KB Output is correct
3 Correct 98 ms 39008 KB Output is correct
4 Correct 107 ms 39400 KB Output is correct
5 Correct 113 ms 39348 KB Output is correct
6 Correct 107 ms 39344 KB Output is correct
7 Correct 111 ms 39356 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 4 ms 9684 KB Output is correct
2 Correct 96 ms 39000 KB Output is correct
3 Correct 98 ms 39008 KB Output is correct
4 Correct 107 ms 39400 KB Output is correct
5 Correct 113 ms 39348 KB Output is correct
6 Correct 107 ms 39344 KB Output is correct
7 Correct 111 ms 39356 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 198 ms 45624 KB Output is correct
11 Correct 104 ms 39056 KB Output is correct
12 Correct 99 ms 39036 KB Output is correct
13 Correct 96 ms 39132 KB Output is correct
14 Correct 209 ms 45292 KB Output is correct
15 Correct 204 ms 46168 KB Output is correct
16 Correct 202 ms 45744 KB Output is correct
17 Correct 208 ms 45804 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 39000 KB Output is correct
3 Correct 98 ms 39008 KB Output is correct
4 Correct 107 ms 39400 KB Output is correct
5 Correct 113 ms 39348 KB Output is correct
6 Correct 107 ms 39344 KB Output is correct
7 Correct 111 ms 39356 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 198 ms 45624 KB Output is correct
11 Correct 104 ms 39056 KB Output is correct
12 Correct 99 ms 39036 KB Output is correct
13 Correct 96 ms 39132 KB Output is correct
14 Correct 209 ms 45292 KB Output is correct
15 Correct 204 ms 46168 KB Output is correct
16 Correct 202 ms 45744 KB Output is correct
17 Correct 208 ms 45804 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 243 ms 45176 KB Output is correct
20 Correct 247 ms 44796 KB Output is correct
21 Correct 258 ms 43104 KB Output is correct
22 Correct 245 ms 41292 KB Output is correct
23 Correct 198 ms 42300 KB Output is correct
24 Correct 201 ms 41384 KB Output is correct
25 Correct 214 ms 41456 KB Output is correct
26 Correct 173 ms 43704 KB Output is correct
27 Correct 163 ms 45492 KB Output is correct
28 Correct 255 ms 44980 KB Output is correct
29 Correct 228 ms 43796 KB Output is correct
30 Correct 215 ms 41408 KB Output is correct
31 Correct 169 ms 45584 KB Output is correct
32 Correct 220 ms 39756 KB Output is correct
33 Correct 222 ms 47504 KB Output is correct
34 Correct 197 ms 41840 KB Output is correct
35 Correct 190 ms 41452 KB Output is correct
36 Correct 155 ms 40300 KB Output is correct
37 Correct 180 ms 40260 KB Output is correct
38 Correct 201 ms 44188 KB Output is correct
39 Correct 190 ms 39600 KB Output is correct
40 Correct 215 ms 43884 KB Output is correct
41 Correct 234 ms 39036 KB Output is correct
42 Correct 220 ms 39080 KB Output is correct
43 Correct 206 ms 40496 KB Output is correct
44 Correct 245 ms 40456 KB Output is correct
45 Correct 233 ms 40876 KB Output is correct
46 Correct 215 ms 40380 KB Output is correct
47 Correct 220 ms 40772 KB Output is correct
48 Correct 248 ms 40728 KB Output is correct
49 Correct 308 ms 39284 KB Output is correct
50 Correct 279 ms 44348 KB Output is correct
51 Correct 183 ms 41064 KB Output is correct
52 Correct 191 ms 40552 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 39000 KB Output is correct
3 Correct 98 ms 39008 KB Output is correct
4 Correct 107 ms 39400 KB Output is correct
5 Correct 113 ms 39348 KB Output is correct
6 Correct 107 ms 39344 KB Output is correct
7 Correct 111 ms 39356 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 198 ms 45624 KB Output is correct
11 Correct 104 ms 39056 KB Output is correct
12 Correct 99 ms 39036 KB Output is correct
13 Correct 96 ms 39132 KB Output is correct
14 Correct 209 ms 45292 KB Output is correct
15 Correct 204 ms 46168 KB Output is correct
16 Correct 202 ms 45744 KB Output is correct
17 Correct 208 ms 45804 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 243 ms 45176 KB Output is correct
20 Correct 247 ms 44796 KB Output is correct
21 Correct 258 ms 43104 KB Output is correct
22 Correct 245 ms 41292 KB Output is correct
23 Correct 198 ms 42300 KB Output is correct
24 Correct 201 ms 41384 KB Output is correct
25 Correct 214 ms 41456 KB Output is correct
26 Correct 173 ms 43704 KB Output is correct
27 Correct 163 ms 45492 KB Output is correct
28 Correct 255 ms 44980 KB Output is correct
29 Correct 228 ms 43796 KB Output is correct
30 Correct 215 ms 41408 KB Output is correct
31 Correct 169 ms 45584 KB Output is correct
32 Correct 220 ms 39756 KB Output is correct
33 Correct 222 ms 47504 KB Output is correct
34 Correct 197 ms 41840 KB Output is correct
35 Correct 190 ms 41452 KB Output is correct
36 Correct 155 ms 40300 KB Output is correct
37 Correct 180 ms 40260 KB Output is correct
38 Correct 201 ms 44188 KB Output is correct
39 Correct 190 ms 39600 KB Output is correct
40 Correct 215 ms 43884 KB Output is correct
41 Correct 234 ms 39036 KB Output is correct
42 Correct 220 ms 39080 KB Output is correct
43 Correct 206 ms 40496 KB Output is correct
44 Correct 245 ms 40456 KB Output is correct
45 Correct 233 ms 40876 KB Output is correct
46 Correct 215 ms 40380 KB Output is correct
47 Correct 220 ms 40772 KB Output is correct
48 Correct 248 ms 40728 KB Output is correct
49 Correct 308 ms 39284 KB Output is correct
50 Correct 279 ms 44348 KB Output is correct
51 Correct 183 ms 41064 KB Output is correct
52 Correct 191 ms 40552 KB Output is correct
53 Runtime error 13 ms 19540 KB Execution killed with signal 6
54 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 9740 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 9740 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 39000 KB Output is correct
3 Correct 98 ms 39008 KB Output is correct
4 Correct 107 ms 39400 KB Output is correct
5 Correct 113 ms 39348 KB Output is correct
6 Correct 107 ms 39344 KB Output is correct
7 Correct 111 ms 39356 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 198 ms 45624 KB Output is correct
11 Correct 104 ms 39056 KB Output is correct
12 Correct 99 ms 39036 KB Output is correct
13 Correct 96 ms 39132 KB Output is correct
14 Correct 209 ms 45292 KB Output is correct
15 Correct 204 ms 46168 KB Output is correct
16 Correct 202 ms 45744 KB Output is correct
17 Correct 208 ms 45804 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 243 ms 45176 KB Output is correct
20 Correct 247 ms 44796 KB Output is correct
21 Correct 258 ms 43104 KB Output is correct
22 Correct 245 ms 41292 KB Output is correct
23 Correct 198 ms 42300 KB Output is correct
24 Correct 201 ms 41384 KB Output is correct
25 Correct 214 ms 41456 KB Output is correct
26 Correct 173 ms 43704 KB Output is correct
27 Correct 163 ms 45492 KB Output is correct
28 Correct 255 ms 44980 KB Output is correct
29 Correct 228 ms 43796 KB Output is correct
30 Correct 215 ms 41408 KB Output is correct
31 Correct 169 ms 45584 KB Output is correct
32 Correct 220 ms 39756 KB Output is correct
33 Correct 222 ms 47504 KB Output is correct
34 Correct 197 ms 41840 KB Output is correct
35 Correct 190 ms 41452 KB Output is correct
36 Correct 155 ms 40300 KB Output is correct
37 Correct 180 ms 40260 KB Output is correct
38 Correct 201 ms 44188 KB Output is correct
39 Correct 190 ms 39600 KB Output is correct
40 Correct 215 ms 43884 KB Output is correct
41 Correct 234 ms 39036 KB Output is correct
42 Correct 220 ms 39080 KB Output is correct
43 Correct 206 ms 40496 KB Output is correct
44 Correct 245 ms 40456 KB Output is correct
45 Correct 233 ms 40876 KB Output is correct
46 Correct 215 ms 40380 KB Output is correct
47 Correct 220 ms 40772 KB Output is correct
48 Correct 248 ms 40728 KB Output is correct
49 Correct 308 ms 39284 KB Output is correct
50 Correct 279 ms 44348 KB Output is correct
51 Correct 183 ms 41064 KB Output is correct
52 Correct 191 ms 40552 KB Output is correct
53 Runtime error 13 ms 19540 KB Execution killed with signal 6
54 Halted 0 ms 0 KB -