oj.uz

Submission #1087937

# Submission time Handle Problem Language Result Execution time Memory
1087937 2024-09-13T14:53:11 Z vladilius Reconstruction Project (JOI22_reconstruction) C++17
31 / 100
 330 ms 427600 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int inf = 1e9 + 5;
const int N = 5e2;

struct dsu{
    int sz[N + 1], p[N + 1];
    int n;
    void init(int ns){
        n = ns;
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
    bool same(int x, int y){
        return get(x) == get(y);
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<arr3> ed;
    for (int i = 1; i <= m; i++){
        int a, b, w; cin>>a>>b>>w;
        ed.pb({a, b, w});
    }
    
    int q; cin>>q;
    vector<int> x(q + 1);
    vector<ll> out(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>x[i];
    }
    
    auto cmp = [&](arr3& x, arr3& y){
        return x[2] < y[2];
    };
    sort(ed.begin(), ed.end(), cmp);
    vector<int> ws;
    for (int i = 0; i < m; i++) ws.pb(ed[i][2]);
    
    vector<int> :: iterator it1, it2;
    dsu T[m];
    for (int i = 0; i < m; i++) T[i].init(n);
    
    vector<ll> p1(q + 2);
    vector<int> p2(q + 2);
    
    for (int i = m - 1; i >= 0; i--){
        auto [a, b, w] = ed[i];

        int l = i, r = m - 1;
        while (l + 1 < r){
            int k = (l + r) / 2;
            if (T[k].same(a, b)){
                r = k - 1;
            }
            else {
                l = k;
            }
        }
        if (!T[r].same(a, b)) l = r;
        
        if (m <= 1000){
            if (l == (m - 1)) l = inf;
            else l = (ws[l + 1] + w - 1) / 2;
            
            it1 = lower_bound(x.begin() + 1, x.end(), w);
            it2 = upper_bound(x.begin() + 1, x.end(), l);
            l = (int) (it1 - x.begin()); r = (int) (it2 - x.begin());
            if (l > r) continue;
            p1[l] -= w; p1[r] += w;
            p2[l]++; p2[r]--;
            
            for (int j = i; j < m; j++){
                if (T[j].same(a, b)) continue;
                T[j].unite(a, b);
            }
        }
    }
    
    if (m > 1000) return 0;
    
    for (int i = 0; i < m; i++) T[i].clear();
    
    for (int i = 0; i < m; i++){
        auto [a, b, w] = ed[i];
        
        int l = 0, r = i;
        while (l + 1 < r){
            int k = (l + r) / 2;
            if (T[k].same(a, b)){
                l = k + 1;
            }
            else {
                r = k;
            }
        }
        if (!T[l].same(a, b)) r = l;

        if (!r) r = 0;
        else r = (ws[r - 1] + w + 1) / 2;
 
        it1 = lower_bound(x.begin() + 1, x.end(), r);
        it2 = lower_bound(x.begin() + 1, x.end(), w);
        l = (int) (it1 - x.begin()); r = (int)(it2 - x.begin());
        if (l > r) continue;
        p1[l] += w; p1[r] -= w;
        p2[l]--; p2[r]++;

        for (int j = i; j >= 0; j--){
            if (T[j].same(a, b)) continue;
            T[j].unite(a, b);
        }
    }
    
    ll s1 = 0; int s2 = 0;
    for (int i = 1; i <= q; i++){
        s1 += p1[i];
        s2 += p2[i];
        cout<<1LL * x[i] * s2 + s1<<"\n";
    }
}

Subtask #1
3.0 / 3.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 258 ms 396684 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 330 ms 427600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 143 ms 48028 KB Output is correct
21 Correct 150 ms 48088 KB Output is correct
22 Correct 169 ms 47912 KB Output is correct
23 Correct 143 ms 47952 KB Output is correct
24 Correct 144 ms 48056 KB Output is correct
25 Correct 140 ms 47956 KB Output is correct
26 Correct 146 ms 47956 KB Output is correct
27 Correct 135 ms 47952 KB Output is correct
28 Correct 136 ms 47956 KB Output is correct
29 Correct 144 ms 47836 KB Output is correct
30 Correct 137 ms 48152 KB Output is correct
31 Correct 142 ms 48064 KB Output is correct
32 Correct 140 ms 48492 KB Output is correct
33 Correct 148 ms 48108 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 258 ms 396684 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 258 ms 396684 KB Output isn't correct
21 Halted 0 ms 0 KB -