oj.uz

Submission #796229

# Submission time Handle Problem Language Result Execution time Memory
796229 2023-07-28T08:13:55 Z 반딧불(#10068) Security Guard (JOI23_guard) C++17
25 / 100
 171 ms 45256 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);
        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;

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;
        }
        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 5 ms 9780 KB Output is correct
2 Correct 78 ms 36020 KB Output is correct
3 Correct 80 ms 35904 KB Output is correct
4 Correct 80 ms 35940 KB Output is correct
5 Correct 79 ms 35988 KB Output is correct
6 Correct 80 ms 35948 KB Output is correct
7 Correct 82 ms 35940 KB Output is correct
8 Correct 4 ms 9756 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9780 KB Output is correct
2 Correct 78 ms 36020 KB Output is correct
3 Correct 80 ms 35904 KB Output is correct
4 Correct 80 ms 35940 KB Output is correct
5 Correct 79 ms 35988 KB Output is correct
6 Correct 80 ms 35948 KB Output is correct
7 Correct 82 ms 35940 KB Output is correct
8 Correct 4 ms 9756 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 87 ms 35940 KB Output is correct
11 Correct 97 ms 35992 KB Output is correct
12 Correct 95 ms 35916 KB Output is correct
13 Correct 90 ms 36008 KB Output is correct
14 Correct 90 ms 35976 KB Output is correct
15 Correct 88 ms 35920 KB Output is correct
16 Correct 87 ms 36040 KB Output is correct
17 Correct 88 ms 35936 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9780 KB Output is correct
2 Correct 78 ms 36020 KB Output is correct
3 Correct 80 ms 35904 KB Output is correct
4 Correct 80 ms 35940 KB Output is correct
5 Correct 79 ms 35988 KB Output is correct
6 Correct 80 ms 35948 KB Output is correct
7 Correct 82 ms 35940 KB Output is correct
8 Correct 4 ms 9756 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 87 ms 35940 KB Output is correct
11 Correct 97 ms 35992 KB Output is correct
12 Correct 95 ms 35916 KB Output is correct
13 Correct 90 ms 36008 KB Output is correct
14 Correct 90 ms 35976 KB Output is correct
15 Correct 88 ms 35920 KB Output is correct
16 Correct 87 ms 36040 KB Output is correct
17 Correct 88 ms 35936 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Incorrect 171 ms 45256 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9780 KB Output is correct
2 Correct 78 ms 36020 KB Output is correct
3 Correct 80 ms 35904 KB Output is correct
4 Correct 80 ms 35940 KB Output is correct
5 Correct 79 ms 35988 KB Output is correct
6 Correct 80 ms 35948 KB Output is correct
7 Correct 82 ms 35940 KB Output is correct
8 Correct 4 ms 9756 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 87 ms 35940 KB Output is correct
11 Correct 97 ms 35992 KB Output is correct
12 Correct 95 ms 35916 KB Output is correct
13 Correct 90 ms 36008 KB Output is correct
14 Correct 90 ms 35976 KB Output is correct
15 Correct 88 ms 35920 KB Output is correct
16 Correct 87 ms 36040 KB Output is correct
17 Correct 88 ms 35936 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Incorrect 171 ms 45256 KB Output isn't correct
20 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 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 5 ms 9684 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 5 ms 9780 KB Output is correct
2 Correct 78 ms 36020 KB Output is correct
3 Correct 80 ms 35904 KB Output is correct
4 Correct 80 ms 35940 KB Output is correct
5 Correct 79 ms 35988 KB Output is correct
6 Correct 80 ms 35948 KB Output is correct
7 Correct 82 ms 35940 KB Output is correct
8 Correct 4 ms 9756 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 87 ms 35940 KB Output is correct
11 Correct 97 ms 35992 KB Output is correct
12 Correct 95 ms 35916 KB Output is correct
13 Correct 90 ms 36008 KB Output is correct
14 Correct 90 ms 35976 KB Output is correct
15 Correct 88 ms 35920 KB Output is correct
16 Correct 87 ms 36040 KB Output is correct
17 Correct 88 ms 35936 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Incorrect 171 ms 45256 KB Output isn't correct
20 Halted 0 ms 0 KB -