Submission #950454

#	Time	Username	Problem	Language	Result	Execution time	Memory
950454		socpite	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5095 ms	64116 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;

int n, m;

vector<pair<int, pair<int, int>>> E;

int cl[maxn];
set<pair<int, int>> tree[maxn];
pair<int, int> X[maxn];

long long fans[maxn];

int pos = -1;

bool dfs(int x, int p, int t, int md){
    if(x == t)return true;
    for(auto v: tree[x]){
        if(v.first == p)continue;
        if(dfs(v.first, x, t, md)){
            if(pos == -1 || (!md && v.second < pos) || (md && v.second > pos))pos = v.second;
            return 1;
        }
    }
    return false;
}

int up[maxn];

int Find(int x){
    return up[x] ? up[x] = Find(up[x]) : x;
}

bool check(int a, int b){
    return Find(a) != Find(b);
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    up[a] = b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    E.resize(m);
    for(auto &v: E)cin >> v.second.first >> v.second.second >> v.first;
    sort(E.begin(), E.end());
    set<int, greater<int>> lside;
    set<int> rside;
    for(int i = 0; i < m; i++){
        pos = -1;
        dfs(E[i].second.first, 0, E[i].second.second, 0);
        cl[i] = pos;
        if(pos != -1){
            lside.erase(pos);
            tree[E[pos].second.first].erase({E[pos].second.second, pos});
            tree[E[pos].second.second].erase({E[pos].second.first, pos});
        }
        lside.insert(i);
        tree[E[i].second.first].insert({E[i].second.second, i});
        tree[E[i].second.second].insert({E[i].second.first, i});
    }
    for(int i = 1; i <= n; i++)tree[i].clear();
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> X[i].first;
        X[i].second = i;
    }
    sort(X, X+q);
    int ptr = m-1;
    for(int i = q-1; i >= 0; i--){
        while(ptr >= 0 && E[ptr].first >= X[i].first){
            pos = -1;
            dfs(E[ptr].second.first, 0, E[ptr].second.second, 1);
            if(pos != -1){
                rside.erase(pos);
                tree[E[pos].second.first].erase({E[pos].second.second, pos});
                tree[E[pos].second.second].erase({E[pos].second.first, pos});
            }
            rside.insert(ptr);
            tree[E[ptr].second.first].insert({E[ptr].second.second, ptr});
            tree[E[ptr].second.second].insert({E[ptr].second.first, ptr});

            lside.erase(ptr);
            if(cl[ptr] != -1)lside.insert(cl[ptr]);
            ptr--;
        }
        auto itl = lside.begin(), itr = rside.begin();
        long long ans = 0;
        for(int j = 1; j <= n; j++)up[j] = 0;
        for(int j = 0; j < n-1; j++){
            while(itl != lside.end() && !check(E[*itl].second.first, E[*itl].second.second))itl++;
            while(itr != rside.end() && !check(E[*itr].second.first, E[*itr].second.second))itr++;
            if(itr == rside.end() || (itl != lside.end() && X[i].first - E[*itl].first < E[*itr].first - X[i].first)){
                Union(E[*itl].second.first, E[*itl].second.second);
                ans += X[i].first - E[*itl].first;
                itl++;
            }
            else {
                Union(E[*itr].second.first, E[*itr].second.second);
                ans += E[*itr].first - X[i].first;
                itr++;
            }
        }
        fans[X[i].second] = ans;
    }
    for(int i = 0; i < q; i++)cout << fans[i] << "\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23