oj.uz

Submission #754907

# Submission time Handle Problem Language Result Execution time Memory
754907 2023-06-08T21:50:10 Z definitelynotmee Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 819 ms 29520 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

struct edge{
    int a, b, w;
    edge(int x = 0, int y = 0, int z = 0){
        a = x;
        b = y;
        w = z;
    }
    bool operator < (edge other) const{
        if(w == other.w){
            return make_pair(a,b) < make_pair(other.a,other.b);
        }
        return w < other.w;
    }
    bool operator == (edge other) const{
        return a == other.a and b == other.b and w == other.w;
    }

    string print(){
        string ret = to_string(a) + ' ' + to_string(b) + ' ' + to_string(w);
        return ret;
    }
};

struct UnionFind{
    vector<int> pai;

    UnionFind(int n = 0){
        pai = vector<int>(n);
        iota(all(pai),0);
    }

    int find(int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }

    bool onion(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b)
            return 0;
        pai[a] = b;
        return 1;
    }

    bool check(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b)
            return 0;
        return 1;
    }
};

struct MST{
    matrix<edge> g;

    MST(int n = 0){
        g = matrix<edge>(n);
    }

    edge dfs(int id, int last, int target){
        edge def(0,0,2e9);
        if(id == target)
            return edge(0,0,2e9-5);
        // cerr << "id = " << id << endl;
        for(auto [a, viz, w]: g[id]){
            if(viz == last)
                continue;
            // cerr << "aresta " << a << ' ' << viz << endl;
            edge cur = dfs(viz,id,target);
            if(cur < def){
                return min(cur,edge(a,viz,w));
            }
        }
        return def;
    }

    void insert(edge x){
        g[x.a].push_back(x);
        swap(x.a,x.b);
        g[x.a].push_back(x);
    }

    void erase(edge x){
        // cout << x.a << " -> ";
        // for(auto& [a,b,c] : g[x.a]){
            // cout <<b << ' ';
        // }
        // cout << endl;
        g[x.a].erase(find(all(g[x.a]),x));
        swap(x.a,x.b);
        g[x.a].erase(find(all(g[x.a]),x));
    }

    edge update(edge x){
        edge ret = dfs(x.a,-1,x.b);
        // cerr << ret.w << endl;
        if(ret.w <= 1e9)
            erase(ret);

        insert(x);
        if(ret.a > ret.b)
            swap(ret.a,ret.b);

        return ret;
    }

};


int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, m;

    cin >> n >> m;

    vector<edge> v(m);

    for(auto & [a, b, w] : v){
        cin >> a >> b >> w;
        a--,b--;
        if(a > b)
            swap(a,b);
    }

    sort(all(v));

    vector<int> entra(m), sai(m,2e9);

    MST mst(n);

    for(int i = 0; i < m; i++){
        // cerr << i << endl;
        // cerr << v[i].a << ' ' << v[i].b << ' ' << v[i].w << endl;
        edge cur = v[i];

        edge popado = mst.update(cur);

        if(popado.w <= 1e9){
            // cerr << "entrou" << endl;
            int id = lower_bound(all(v),popado)-v.begin();
            int turning_point = (cur.w+popado.w+1)/2;
            entra[i] = turning_point;
            sai[id] = turning_point;
        }
    }

    vector<int> oentra(m), osai(m), ov(m);
    
    auto setup =[&](vector<int> & o, auto& v){
        iota(all(o),0);
        sort(all(o), [&](int a, int b){
            return v[a] < v[b];
        });
    };


    setup(oentra,entra);
    setup(osai,sai);
    setup(ov,v);

    int pentra = 0, psai = 0, pv = 0;

    int q;
    cin >> q;

    ll qtd = 0;
    ll resp = 0;

    while(q--){
        ll x;
        cin >> x;

        
        
        // cerr << "x = " << x << endl;

        while(pentra < m && entra[oentra[pentra]] <= x){
            // cerr << "entra " << v[oentra[pentra]].print() << '\n';
            
            qtd--;
            resp+=v[oentra[pentra]].w;
            pentra++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }
        while(pv < m && v[ov[pv]].w <= x){
            // cerr << "change " << v[ov[pv]].print() << '\n';
            
            qtd+=2;
            resp-=2*v[ov[pv]].w;
            pv++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }
        while(psai < m && sai[osai[psai]] <= x){
            // cerr << "sai " << v[osai[psai]].print() << '\n';
            
            qtd--;
            resp+=v[osai[psai]].w;
            psai++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }

        cout << resp +qtd*x<< '\n';
    }



}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 606 ms 3520 KB Output is correct
21 Correct 328 ms 3632 KB Output is correct
22 Correct 496 ms 3560 KB Output is correct
23 Correct 537 ms 3608 KB Output is correct
24 Correct 524 ms 3544 KB Output is correct
25 Correct 564 ms 3540 KB Output is correct
26 Correct 605 ms 3672 KB Output is correct
27 Correct 572 ms 3524 KB Output is correct
28 Correct 601 ms 3536 KB Output is correct
29 Correct 319 ms 3808 KB Output is correct
30 Correct 590 ms 3544 KB Output is correct
31 Correct 579 ms 3540 KB Output is correct
32 Correct 612 ms 3520 KB Output is correct
33 Correct 565 ms 3648 KB Output is correct
34 Correct 314 ms 5180 KB Output is correct
35 Correct 588 ms 3516 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 447 ms 23952 KB Output is correct
5 Correct 477 ms 25920 KB Output is correct
6 Correct 442 ms 25992 KB Output is correct
7 Correct 258 ms 27848 KB Output is correct
8 Correct 244 ms 27856 KB Output is correct
9 Correct 253 ms 27932 KB Output is correct
10 Correct 461 ms 26052 KB Output is correct
11 Correct 250 ms 27980 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 200 ms 21392 KB Output is correct
21 Correct 183 ms 22348 KB Output is correct
22 Correct 203 ms 22344 KB Output is correct
23 Correct 199 ms 22296 KB Output is correct
24 Correct 192 ms 22244 KB Output is correct
25 Correct 222 ms 22268 KB Output is correct
26 Correct 192 ms 22600 KB Output is correct
27 Correct 278 ms 22348 KB Output is correct
28 Correct 202 ms 22248 KB Output is correct
29 Correct 222 ms 22332 KB Output is correct
30 Correct 188 ms 22392 KB Output is correct
31 Correct 193 ms 22096 KB Output is correct
32 Correct 192 ms 22864 KB Output is correct
33 Correct 187 ms 22216 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 606 ms 3520 KB Output is correct
21 Correct 328 ms 3632 KB Output is correct
22 Correct 496 ms 3560 KB Output is correct
23 Correct 537 ms 3608 KB Output is correct
24 Correct 524 ms 3544 KB Output is correct
25 Correct 564 ms 3540 KB Output is correct
26 Correct 605 ms 3672 KB Output is correct
27 Correct 572 ms 3524 KB Output is correct
28 Correct 601 ms 3536 KB Output is correct
29 Correct 319 ms 3808 KB Output is correct
30 Correct 590 ms 3544 KB Output is correct
31 Correct 579 ms 3540 KB Output is correct
32 Correct 612 ms 3520 KB Output is correct
33 Correct 565 ms 3648 KB Output is correct
34 Correct 314 ms 5180 KB Output is correct
35 Correct 588 ms 3516 KB Output is correct
36 Correct 594 ms 3756 KB Output is correct
37 Correct 330 ms 5900 KB Output is correct
38 Correct 513 ms 5612 KB Output is correct
39 Correct 535 ms 5580 KB Output is correct
40 Correct 509 ms 5576 KB Output is correct
41 Correct 558 ms 5568 KB Output is correct
42 Correct 616 ms 5560 KB Output is correct
43 Correct 630 ms 5648 KB Output is correct
44 Correct 585 ms 5604 KB Output is correct
45 Correct 334 ms 5852 KB Output is correct
46 Correct 591 ms 5556 KB Output is correct
47 Correct 594 ms 5564 KB Output is correct
48 Correct 616 ms 5556 KB Output is correct
49 Correct 584 ms 5608 KB Output is correct
50 Correct 312 ms 7372 KB Output is correct
51 Correct 614 ms 5564 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 606 ms 3520 KB Output is correct
21 Correct 328 ms 3632 KB Output is correct
22 Correct 496 ms 3560 KB Output is correct
23 Correct 537 ms 3608 KB Output is correct
24 Correct 524 ms 3544 KB Output is correct
25 Correct 564 ms 3540 KB Output is correct
26 Correct 605 ms 3672 KB Output is correct
27 Correct 572 ms 3524 KB Output is correct
28 Correct 601 ms 3536 KB Output is correct
29 Correct 319 ms 3808 KB Output is correct
30 Correct 590 ms 3544 KB Output is correct
31 Correct 579 ms 3540 KB Output is correct
32 Correct 612 ms 3520 KB Output is correct
33 Correct 565 ms 3648 KB Output is correct
34 Correct 314 ms 5180 KB Output is correct
35 Correct 588 ms 3516 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 447 ms 23952 KB Output is correct
40 Correct 477 ms 25920 KB Output is correct
41 Correct 442 ms 25992 KB Output is correct
42 Correct 258 ms 27848 KB Output is correct
43 Correct 244 ms 27856 KB Output is correct
44 Correct 253 ms 27932 KB Output is correct
45 Correct 461 ms 26052 KB Output is correct
46 Correct 250 ms 27980 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 200 ms 21392 KB Output is correct
49 Correct 183 ms 22348 KB Output is correct
50 Correct 203 ms 22344 KB Output is correct
51 Correct 199 ms 22296 KB Output is correct
52 Correct 192 ms 22244 KB Output is correct
53 Correct 222 ms 22268 KB Output is correct
54 Correct 192 ms 22600 KB Output is correct
55 Correct 278 ms 22348 KB Output is correct
56 Correct 202 ms 22248 KB Output is correct
57 Correct 222 ms 22332 KB Output is correct
58 Correct 188 ms 22392 KB Output is correct
59 Correct 193 ms 22096 KB Output is correct
60 Correct 192 ms 22864 KB Output is correct
61 Correct 187 ms 22216 KB Output is correct
62 Correct 594 ms 3756 KB Output is correct
63 Correct 330 ms 5900 KB Output is correct
64 Correct 513 ms 5612 KB Output is correct
65 Correct 535 ms 5580 KB Output is correct
66 Correct 509 ms 5576 KB Output is correct
67 Correct 558 ms 5568 KB Output is correct
68 Correct 616 ms 5560 KB Output is correct
69 Correct 630 ms 5648 KB Output is correct
70 Correct 585 ms 5604 KB Output is correct
71 Correct 334 ms 5852 KB Output is correct
72 Correct 591 ms 5556 KB Output is correct
73 Correct 594 ms 5564 KB Output is correct
74 Correct 616 ms 5556 KB Output is correct
75 Correct 584 ms 5608 KB Output is correct
76 Correct 312 ms 7372 KB Output is correct
77 Correct 614 ms 5564 KB Output is correct
78 Correct 800 ms 24900 KB Output is correct
79 Correct 498 ms 26900 KB Output is correct
80 Correct 717 ms 26044 KB Output is correct
81 Correct 705 ms 26036 KB Output is correct
82 Correct 666 ms 25092 KB Output is correct
83 Correct 786 ms 24976 KB Output is correct
84 Correct 767 ms 25004 KB Output is correct
85 Correct 760 ms 24888 KB Output is correct
86 Correct 773 ms 25016 KB Output is correct
87 Correct 515 ms 26824 KB Output is correct
88 Correct 793 ms 24984 KB Output is correct
89 Correct 756 ms 24972 KB Output is correct
90 Correct 795 ms 25160 KB Output is correct
91 Correct 738 ms 24888 KB Output is correct
92 Correct 504 ms 29520 KB Output is correct
93 Correct 819 ms 26052 KB Output is correct