oj.uz

Submission #679074

# Submission time Handle Problem Language Result Execution time Memory
679074 2023-01-07T11:48:37 Z sysia Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 2237 ms 30512 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef DEBUG
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct UF{
    vector<int>rep, sz;
    vector<tuple<int, int, int, int>> st;
    int s;
 
    UF(int n){
        s = n;
        rep.assign(s, 0);
        iota(rep.begin(), rep.end(), 0);
        sz.assign(s, 1);
    }
    int f(int a){return a == rep[a] ? a : f(rep[a]);}
    bool sameset(int a, int b){return f(a) == f(b);}
    void undo(){
        while (st.size()){
            auto [a, b, sA, sB] = st.back();
            st.pop_back();
            rep[a] = a;rep[b] = b;
            sz[a] = sA;sz[b] = sB;
        }
    }
    bool u(int a, int b){
        a = f(a); b = f(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) swap(a, b);
        st.emplace_back(a, b, sz[a], sz[b]);
        sz[a] += sz[b];
        rep[b] = a;
        return 1;
    }
};

struct e{
    int a, b, c;
    e(){}
    e(int _a, int _b, int _c){a = _a, b = _b, c = _c;}
};

void solve(){
    int n, m; cin >> n >> m;
    vector<e>edges;
    for (int i = 0; i<m; i++){
        int a, b, c; cin >> a >> b >> c;
        edges.emplace_back(a, b, c);
    }
    sort(edges.begin(), edges.end(), [](auto a, auto b){return a.c < b.c;});
    UF dsu(n+1);
    vector<int>L(m, -oo), R(m, oo);
    vector<int>used;
    //maksymalnie O(n) krawędzi, zanim nie spróbujemy połączyć czegoś, co już jest w jednej spójnej(;pppp)
    for (int i = 0; i<m; i++){
        auto [a, b, c] = edges[i];
        if (dsu.u(a, b)) {
            used.emplace_back(i);
            continue;
        }
        int what = -1;
        dsu.undo();
        for (int j = (int)used.size()-1; j>=0; j--){
            dsu.u(edges[used[j]].a, edges[used[j]].b);
            if (dsu.sameset(a, b)){
                what = used[j];
                used.erase(used.begin()+j);
                break;
            }
        }
        dsu.undo();
        assert(what != -1);
        used.emplace_back(i);
        int cc = (edges[i].c + edges[what].c + 1)/2;
        L[i] = R[what] = cc;
        // debug(what, i, used);
        for (auto j: used) dsu.u(edges[j].a, edges[j].b);
    } 
    //                      b      a = cnt of bigger than L
    // [-oo, Li) ---> 0     0      0
    // [Li, wi)  ---> wi-x (+wi)   -1
    // [wi, Ri)  ---> x-wi (-2wi)  1 (+2 in pref)
    // [Ri, +oo) ---> 0    (+wi)   0 (-1 in pref)
    vector<pair<int, pair<int, int>>>pref;
    for (int i = 0; i<m; i++){
        auto [a, b, c] = edges[i];
        pref.emplace_back(L[i], T{-1, c});
        pref.emplace_back(c, T{2, -2*c});
        pref.emplace_back(R[i], T{-1, c});
        // debug(a, b, c, L[i], R[i]);
    }
    sort(pref.begin(), pref.end());
    int ptr = 0, a = 0, b = 0;
    int q; cin >> q;
    while (q--){
        int x; cin >> x; 
        while (ptr < (int)pref.size() && pref[ptr].first <= x){
            a += pref[ptr].second.first;
            b += pref[ptr].second.second;
            ptr++;
        }
        cout << a * x + b << "\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2084 ms 18392 KB Output is correct
21 Correct 1426 ms 18392 KB Output is correct
22 Correct 1473 ms 18384 KB Output is correct
23 Correct 1538 ms 18388 KB Output is correct
24 Correct 1784 ms 18392 KB Output is correct
25 Correct 1993 ms 18392 KB Output is correct
26 Correct 2065 ms 18396 KB Output is correct
27 Correct 2062 ms 18456 KB Output is correct
28 Correct 2037 ms 18484 KB Output is correct
29 Correct 2049 ms 18480 KB Output is correct
30 Correct 2050 ms 18396 KB Output is correct
31 Correct 2050 ms 18392 KB Output is correct
32 Correct 2036 ms 18392 KB Output is correct
33 Correct 2049 ms 18396 KB Output is correct
34 Correct 2036 ms 18616 KB Output is correct
35 Correct 2051 ms 18388 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1730 ms 28324 KB Output is correct
5 Correct 1717 ms 28516 KB Output is correct
6 Correct 1716 ms 28584 KB Output is correct
7 Correct 912 ms 30284 KB Output is correct
8 Correct 773 ms 30512 KB Output is correct
9 Correct 740 ms 30344 KB Output is correct
10 Correct 1709 ms 28420 KB Output is correct
11 Correct 779 ms 30472 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 190 ms 18672 KB Output is correct
21 Correct 188 ms 18764 KB Output is correct
22 Correct 194 ms 18696 KB Output is correct
23 Correct 200 ms 18720 KB Output is correct
24 Correct 193 ms 18636 KB Output is correct
25 Correct 199 ms 18636 KB Output is correct
26 Correct 200 ms 18728 KB Output is correct
27 Correct 189 ms 18804 KB Output is correct
28 Correct 198 ms 18676 KB Output is correct
29 Correct 188 ms 18688 KB Output is correct
30 Correct 198 ms 18664 KB Output is correct
31 Correct 188 ms 18736 KB Output is correct
32 Correct 190 ms 19276 KB Output is correct
33 Correct 189 ms 18568 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2084 ms 18392 KB Output is correct
21 Correct 1426 ms 18392 KB Output is correct
22 Correct 1473 ms 18384 KB Output is correct
23 Correct 1538 ms 18388 KB Output is correct
24 Correct 1784 ms 18392 KB Output is correct
25 Correct 1993 ms 18392 KB Output is correct
26 Correct 2065 ms 18396 KB Output is correct
27 Correct 2062 ms 18456 KB Output is correct
28 Correct 2037 ms 18484 KB Output is correct
29 Correct 2049 ms 18480 KB Output is correct
30 Correct 2050 ms 18396 KB Output is correct
31 Correct 2050 ms 18392 KB Output is correct
32 Correct 2036 ms 18392 KB Output is correct
33 Correct 2049 ms 18396 KB Output is correct
34 Correct 2036 ms 18616 KB Output is correct
35 Correct 2051 ms 18388 KB Output is correct
36 Correct 2058 ms 18584 KB Output is correct
37 Correct 1397 ms 18580 KB Output is correct
38 Correct 1461 ms 18592 KB Output is correct
39 Correct 1552 ms 18584 KB Output is correct
40 Correct 1738 ms 18644 KB Output is correct
41 Correct 1971 ms 18584 KB Output is correct
42 Correct 2029 ms 18584 KB Output is correct
43 Correct 2057 ms 18588 KB Output is correct
44 Correct 2060 ms 18584 KB Output is correct
45 Correct 2043 ms 18588 KB Output is correct
46 Correct 2056 ms 18584 KB Output is correct
47 Correct 2044 ms 18584 KB Output is correct
48 Correct 2047 ms 18584 KB Output is correct
49 Correct 2057 ms 18584 KB Output is correct
50 Correct 2052 ms 18696 KB Output is correct
51 Correct 2059 ms 18588 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2084 ms 18392 KB Output is correct
21 Correct 1426 ms 18392 KB Output is correct
22 Correct 1473 ms 18384 KB Output is correct
23 Correct 1538 ms 18388 KB Output is correct
24 Correct 1784 ms 18392 KB Output is correct
25 Correct 1993 ms 18392 KB Output is correct
26 Correct 2065 ms 18396 KB Output is correct
27 Correct 2062 ms 18456 KB Output is correct
28 Correct 2037 ms 18484 KB Output is correct
29 Correct 2049 ms 18480 KB Output is correct
30 Correct 2050 ms 18396 KB Output is correct
31 Correct 2050 ms 18392 KB Output is correct
32 Correct 2036 ms 18392 KB Output is correct
33 Correct 2049 ms 18396 KB Output is correct
34 Correct 2036 ms 18616 KB Output is correct
35 Correct 2051 ms 18388 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1730 ms 28324 KB Output is correct
40 Correct 1717 ms 28516 KB Output is correct
41 Correct 1716 ms 28584 KB Output is correct
42 Correct 912 ms 30284 KB Output is correct
43 Correct 773 ms 30512 KB Output is correct
44 Correct 740 ms 30344 KB Output is correct
45 Correct 1709 ms 28420 KB Output is correct
46 Correct 779 ms 30472 KB Output is correct
47 Correct 0 ms 320 KB Output is correct
48 Correct 190 ms 18672 KB Output is correct
49 Correct 188 ms 18764 KB Output is correct
50 Correct 194 ms 18696 KB Output is correct
51 Correct 200 ms 18720 KB Output is correct
52 Correct 193 ms 18636 KB Output is correct
53 Correct 199 ms 18636 KB Output is correct
54 Correct 200 ms 18728 KB Output is correct
55 Correct 189 ms 18804 KB Output is correct
56 Correct 198 ms 18676 KB Output is correct
57 Correct 188 ms 18688 KB Output is correct
58 Correct 198 ms 18664 KB Output is correct
59 Correct 188 ms 18736 KB Output is correct
60 Correct 190 ms 19276 KB Output is correct
61 Correct 189 ms 18568 KB Output is correct
62 Correct 2058 ms 18584 KB Output is correct
63 Correct 1397 ms 18580 KB Output is correct
64 Correct 1461 ms 18592 KB Output is correct
65 Correct 1552 ms 18584 KB Output is correct
66 Correct 1738 ms 18644 KB Output is correct
67 Correct 1971 ms 18584 KB Output is correct
68 Correct 2029 ms 18584 KB Output is correct
69 Correct 2057 ms 18588 KB Output is correct
70 Correct 2060 ms 18584 KB Output is correct
71 Correct 2043 ms 18588 KB Output is correct
72 Correct 2056 ms 18584 KB Output is correct
73 Correct 2044 ms 18584 KB Output is correct
74 Correct 2047 ms 18584 KB Output is correct
75 Correct 2057 ms 18584 KB Output is correct
76 Correct 2052 ms 18696 KB Output is correct
77 Correct 2059 ms 18588 KB Output is correct
78 Correct 2237 ms 27420 KB Output is correct
79 Correct 1559 ms 29368 KB Output is correct
80 Correct 1624 ms 28380 KB Output is correct
81 Correct 1712 ms 28340 KB Output is correct
82 Correct 1936 ms 27396 KB Output is correct
83 Correct 2149 ms 27468 KB Output is correct
84 Correct 2218 ms 27300 KB Output is correct
85 Correct 2227 ms 27320 KB Output is correct
86 Correct 2210 ms 27460 KB Output is correct
87 Correct 2204 ms 29036 KB Output is correct
88 Correct 2215 ms 27376 KB Output is correct
89 Correct 2213 ms 27276 KB Output is correct
90 Correct 2215 ms 27392 KB Output is correct
91 Correct 2216 ms 27396 KB Output is correct
92 Correct 2207 ms 30160 KB Output is correct
93 Correct 2224 ms 28528 KB Output is correct