oj.uz

Submission #759056

# Submission time Handle Problem Language Result Execution time Memory
759056 2023-06-15T17:38:54 Z Lobo Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1160 ms 852836 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 550;
const int maxm = 1e5+10;

int n, m, q, cl[maxm], cr[maxm];
vector<int> mstl[maxm], mstr[maxm], gms[maxn];
vector<pair<int,pair<int,int>>> edges;

int dfsmini(int u, int ed, int anti) {
    if(u == ed) return m;
    for(auto i : gms[u]) if(i != anti) {
        int v = edges[i].sc.fr+edges[i].sc.sc-u;
        int ret = dfsmini(v,ed,i);
        if(ret != -1) return min(ret,i);
    }
    return -1;
}

int dfsmaxi(int u, int ed, int anti) {
    if(u == ed) return 0;
    for(auto i : gms[u]) if(i != anti) {
        int v = edges[i].sc.fr+edges[i].sc.sc-u;
        int ret = dfsmaxi(v,ed,i);
        if(ret != -1) return max(ret,i);
    }
    return -1;
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;

        edges.pb(mp(w,mp(u,v)));
    }
    sort(all(edges));

    for(int i = 0; i < m; i++) {
        if(i == 0) {
            mstl[i].pb(i);
            gms[edges[i].sc.fr].pb(i);
            gms[edges[i].sc.sc].pb(i);
            cl[i] = 0;
        }
        else {
            mstl[i] = mstl[i-1];
            int ui = edges[i].sc.fr;
            int vi = edges[i].sc.sc;

            int j = dfsmini(ui,vi,-1);
            
            if(j == -1) {
                mstl[i].pb(i);
                gms[edges[i].sc.fr].pb(i);
                gms[edges[i].sc.sc].pb(i);
                cl[i] = 0;
            }
            else {
                cl[i] = (edges[i].fr+edges[j].fr+1+(2-1))/2;
                auto it1 = find(all(mstl[i]),j);
                mstl[i].erase(it1);
                auto it2 = find(all(gms[edges[j].sc.fr]),j);
                gms[edges[j].sc.fr].erase(it2);
                auto it3 = find(all(gms[edges[j].sc.sc]),j);
                gms[edges[j].sc.sc].erase(it3);

                mstl[i].pb(i);
                gms[ui].pb(i);
                gms[vi].pb(i);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        gms[i].clear();
    }

    for(int i = m-1; i >= 0; i--) {
        if(i == m-1) {
            mstr[i].pb(i);
            gms[edges[i].sc.fr].pb(i);
            gms[edges[i].sc.sc].pb(i);
            cr[i] = inf;
        }
        else {
            mstr[i] = mstr[i+1];
            int ui = edges[i].sc.fr;
            int vi = edges[i].sc.sc;

            int j = dfsmaxi(ui,vi,-1);
            if(j == -1) {
                mstr[i].pb(i);
                gms[edges[i].sc.fr].pb(i);
                gms[edges[i].sc.sc].pb(i);
                cr[i] = inf;
            }
            else {
                cr[i] = (edges[i].fr+edges[j].fr)/2;

                auto it1 = find(all(mstr[i]),j);
                mstr[i].erase(it1);

                auto it2 = find(all(gms[edges[j].sc.fr]),j);
                gms[edges[j].sc.fr].erase(it2);
                auto it3 = find(all(gms[edges[j].sc.sc]),j);
                gms[edges[j].sc.sc].erase(it3);

                mstr[i].pb(i);
                gms[ui].pb(i);
                gms[vi].pb(i);
            }
        }
    }

    cin >> q;
    vector<pair<int,pair<int,int>>> qrs;
    for(int i = 0; i < q; i++) {
        int c; cin >> c;
        qrs.pb(mp(c,mp(0,i)));
    }
    for(int i = 0; i < m; i++) {
        qrs.pb(mp(cl[i],mp(-1,i)));
        qrs.pb(mp(cr[i],mp(1,i)));
        qrs.pb(mp(edges[i].fr,mp(2,i)));
    }

    sort(all(qrs));

    int ans = 0;
    int qp = 0;
    int qn = 0;
    for(auto X : qrs) {
        if(X.sc.fr == 0) {
            cout << ans+qp*X.fr-qn*X.fr << endl;
        }
        else if(X.sc.fr == -1) {
            qn++;
            ans+= edges[X.sc.sc].fr;
        }
        else if(X.sc.fr == 2) {
            qp++;
            qn--;
            ans-= 2*edges[X.sc.sc].fr;
        }
        else {
            qp--;
            ans+= edges[X.sc.sc].fr;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 4 ms 4924 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5040 KB Output is correct
14 Correct 4 ms 5040 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5040 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 4 ms 4924 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5040 KB Output is correct
14 Correct 4 ms 5040 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5040 KB Output is correct
19 Correct 3 ms 5040 KB Output is correct
20 Correct 1028 ms 805212 KB Output is correct
21 Correct 783 ms 765328 KB Output is correct
22 Correct 908 ms 797088 KB Output is correct
23 Correct 938 ms 804152 KB Output is correct
24 Correct 866 ms 805492 KB Output is correct
25 Correct 986 ms 805776 KB Output is correct
26 Correct 986 ms 806000 KB Output is correct
27 Correct 962 ms 805988 KB Output is correct
28 Correct 968 ms 806052 KB Output is correct
29 Correct 711 ms 792300 KB Output is correct
30 Correct 971 ms 805964 KB Output is correct
31 Correct 970 ms 805956 KB Output is correct
32 Correct 982 ms 806108 KB Output is correct
33 Correct 1035 ms 806012 KB Output is correct
34 Correct 533 ms 678820 KB Output is correct
35 Correct 978 ms 805920 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 971 ms 841844 KB Output is correct
5 Correct 936 ms 851260 KB Output is correct
6 Correct 969 ms 851020 KB Output is correct
7 Correct 510 ms 543256 KB Output is correct
8 Correct 441 ms 480760 KB Output is correct
9 Correct 422 ms 465956 KB Output is correct
10 Correct 941 ms 851064 KB Output is correct
11 Correct 470 ms 480896 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 4 ms 4924 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5040 KB Output is correct
14 Correct 4 ms 5040 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5040 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 235 ms 51296 KB Output is correct
21 Correct 228 ms 51240 KB Output is correct
22 Correct 233 ms 51356 KB Output is correct
23 Correct 252 ms 51336 KB Output is correct
24 Correct 246 ms 51336 KB Output is correct
25 Correct 225 ms 51404 KB Output is correct
26 Correct 223 ms 51560 KB Output is correct
27 Correct 233 ms 51388 KB Output is correct
28 Correct 223 ms 51392 KB Output is correct
29 Correct 227 ms 51472 KB Output is correct
30 Correct 225 ms 51364 KB Output is correct
31 Correct 221 ms 51320 KB Output is correct
32 Correct 223 ms 51516 KB Output is correct
33 Correct 234 ms 51080 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 4 ms 4924 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5040 KB Output is correct
14 Correct 4 ms 5040 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5040 KB Output is correct
19 Correct 3 ms 5040 KB Output is correct
20 Correct 1028 ms 805212 KB Output is correct
21 Correct 783 ms 765328 KB Output is correct
22 Correct 908 ms 797088 KB Output is correct
23 Correct 938 ms 804152 KB Output is correct
24 Correct 866 ms 805492 KB Output is correct
25 Correct 986 ms 805776 KB Output is correct
26 Correct 986 ms 806000 KB Output is correct
27 Correct 962 ms 805988 KB Output is correct
28 Correct 968 ms 806052 KB Output is correct
29 Correct 711 ms 792300 KB Output is correct
30 Correct 971 ms 805964 KB Output is correct
31 Correct 970 ms 805956 KB Output is correct
32 Correct 982 ms 806108 KB Output is correct
33 Correct 1035 ms 806012 KB Output is correct
34 Correct 533 ms 678820 KB Output is correct
35 Correct 978 ms 805920 KB Output is correct
36 Correct 1024 ms 806196 KB Output is correct
37 Correct 822 ms 766324 KB Output is correct
38 Correct 909 ms 796980 KB Output is correct
39 Correct 914 ms 804500 KB Output is correct
40 Correct 863 ms 805784 KB Output is correct
41 Correct 937 ms 806060 KB Output is correct
42 Correct 950 ms 806128 KB Output is correct
43 Correct 967 ms 806200 KB Output is correct
44 Correct 964 ms 806276 KB Output is correct
45 Correct 694 ms 792428 KB Output is correct
46 Correct 986 ms 806168 KB Output is correct
47 Correct 971 ms 806380 KB Output is correct
48 Correct 963 ms 806200 KB Output is correct
49 Correct 950 ms 806192 KB Output is correct
50 Correct 516 ms 678936 KB Output is correct
51 Correct 952 ms 806072 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5032 KB Output is correct
5 Correct 4 ms 4924 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5040 KB Output is correct
14 Correct 4 ms 5040 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5040 KB Output is correct
19 Correct 3 ms 5040 KB Output is correct
20 Correct 1028 ms 805212 KB Output is correct
21 Correct 783 ms 765328 KB Output is correct
22 Correct 908 ms 797088 KB Output is correct
23 Correct 938 ms 804152 KB Output is correct
24 Correct 866 ms 805492 KB Output is correct
25 Correct 986 ms 805776 KB Output is correct
26 Correct 986 ms 806000 KB Output is correct
27 Correct 962 ms 805988 KB Output is correct
28 Correct 968 ms 806052 KB Output is correct
29 Correct 711 ms 792300 KB Output is correct
30 Correct 971 ms 805964 KB Output is correct
31 Correct 970 ms 805956 KB Output is correct
32 Correct 982 ms 806108 KB Output is correct
33 Correct 1035 ms 806012 KB Output is correct
34 Correct 533 ms 678820 KB Output is correct
35 Correct 978 ms 805920 KB Output is correct
36 Correct 3 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 2 ms 4948 KB Output is correct
39 Correct 971 ms 841844 KB Output is correct
40 Correct 936 ms 851260 KB Output is correct
41 Correct 969 ms 851020 KB Output is correct
42 Correct 510 ms 543256 KB Output is correct
43 Correct 441 ms 480760 KB Output is correct
44 Correct 422 ms 465956 KB Output is correct
45 Correct 941 ms 851064 KB Output is correct
46 Correct 470 ms 480896 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 235 ms 51296 KB Output is correct
49 Correct 228 ms 51240 KB Output is correct
50 Correct 233 ms 51356 KB Output is correct
51 Correct 252 ms 51336 KB Output is correct
52 Correct 246 ms 51336 KB Output is correct
53 Correct 225 ms 51404 KB Output is correct
54 Correct 223 ms 51560 KB Output is correct
55 Correct 233 ms 51388 KB Output is correct
56 Correct 223 ms 51392 KB Output is correct
57 Correct 227 ms 51472 KB Output is correct
58 Correct 225 ms 51364 KB Output is correct
59 Correct 221 ms 51320 KB Output is correct
60 Correct 223 ms 51516 KB Output is correct
61 Correct 234 ms 51080 KB Output is correct
62 Correct 1024 ms 806196 KB Output is correct
63 Correct 822 ms 766324 KB Output is correct
64 Correct 909 ms 796980 KB Output is correct
65 Correct 914 ms 804500 KB Output is correct
66 Correct 863 ms 805784 KB Output is correct
67 Correct 937 ms 806060 KB Output is correct
68 Correct 950 ms 806128 KB Output is correct
69 Correct 967 ms 806200 KB Output is correct
70 Correct 964 ms 806276 KB Output is correct
71 Correct 694 ms 792428 KB Output is correct
72 Correct 986 ms 806168 KB Output is correct
73 Correct 971 ms 806380 KB Output is correct
74 Correct 963 ms 806200 KB Output is correct
75 Correct 950 ms 806192 KB Output is correct
76 Correct 516 ms 678936 KB Output is correct
77 Correct 952 ms 806072 KB Output is correct
78 Correct 1143 ms 852620 KB Output is correct
79 Correct 863 ms 807072 KB Output is correct
80 Correct 1098 ms 844068 KB Output is correct
81 Correct 1109 ms 850696 KB Output is correct
82 Correct 1041 ms 852104 KB Output is correct
83 Correct 1112 ms 852384 KB Output is correct
84 Correct 1141 ms 852608 KB Output is correct
85 Correct 1155 ms 852836 KB Output is correct
86 Correct 1137 ms 852520 KB Output is correct
87 Correct 882 ms 838760 KB Output is correct
88 Correct 1137 ms 852568 KB Output is correct
89 Correct 1131 ms 852660 KB Output is correct
90 Correct 1158 ms 852712 KB Output is correct
91 Correct 1154 ms 852604 KB Output is correct
92 Correct 714 ms 725388 KB Output is correct
93 Correct 1160 ms 852704 KB Output is correct