Submission #1153474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153474		MPG	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5094 ms	17708 KiB

reconstruction

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
#define pb push_back
//cout << vectorprecision(5) << fixed << f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn = 2e5 + 123;
ll const inf = 2e18;
ll const loG = 23;
//ll const mod = 1e9 + 7;
ll const mod = 998244353;
ll const sq = 350;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}



ll n, m, q, chi[maxn], sz[maxn], par[maxn], cnt;
vector <pair <ll, pair <ll, ll>>> yal;
vector <pair <ll, ll>> edg[maxn];
vector <ll> w;
unordered_map <ll, ll> mp;


ll get(ll v){
    if (par[v] == v)
        return v;
    return par[v] = get(par[v]);
}

bool merge(ll v, ll u){
    v = get(v), u = get(u);
    if (v == u)
        return 0;
    if (sz[v] < sz[u])
        swap(u, v);
    sz[v] += sz[u];
    par[u] = v;
    cnt--;
    return 1;
}




void Solve(){

cin >> n >> m;
for (int i = 1; i < m + 1; i++){
    ll a, b, c; cin >> a >> b >> c;
    yal.push_back({c, {a, b}});
    w.push_back(c);
}
sort(w.begin(), w.end()); w.resize(unique(w.begin(), w.end()) - w.begin());
for (ll x : w){
    mp[x] = lower_bound(w.begin(), w.end(), x) - w.begin() + 1;
    chi[mp[x]] = x;
}
for (auto p : yal){
    edg[mp[p.first]].push_back({p.second.first, p.second.second});
}

//cout << "OK" << endl;
//cout << w.size() << endl;

cin >> q;
while (q--){
    ll x; cin >> x;
    ll r = lower_bound(w.begin(), w.end(), x) - w.begin() + 1;
    ll l = r - 1;
    //cout << l << " " << r << endl;
    for (int i = 1; i < n + 1; i++){
        sz[i] = 1;
        par[i] = i;
    }
    cnt = n;
    ll ans = 0;
    while (cnt > 1){
        ll a = chi[l], b = chi[r];
        //cout << l << " " << r << ' ' << a << ' ' << b << endl;
        if (r > w.size())
            b = inf;
        if (l < 1)
            a = inf;
        if (abs(x - a) < abs(x - b)){
            //cout << "using l" << endl;
            for (auto p : edg[l]){
                //cout << p.first << " " << p.second << endl;
                ans += merge(p.first, p.second) * abs(x - a);
                //cout << "done" << endl;
            }
            l--;
        }
        else{
            //cout << "using r" << endl;
            for (auto p : edg[r]){
                ans += merge(p.first, p.second) * abs(x - b);
            }
            r++;
        }
        //cout << ans << ' ' << cnt << endl;
    }
    cout << ans << endl;
}



}



int main(){
sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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