Submission #550738

#	Time	Username	Problem	Language	Result	Execution time	Memory
550738		BalintR	Reconstruction Project (JOI22_reconstruction)	C++17	35 / 100	922 ms	20480 KiB

reconstruction

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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cout << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}

struct Edge {
    int t, n1, n2;

    bool operator<(Edge e) const {
        return t < e.t;
    }
};

const int H = 10;
const int MN = 505;
const int ME = 1e5 + 5;
const int MQ = 1e6 + 5;
int n, m, q;
vector<Edge> adjList[MN]; // {t, node, id}
int queries[MQ], qi;

bool vis[MN];
set<pii> spanAdjList[MN];
vi spanTree;
Edge edges[ME];
pii nextEvent;

int dep[MN];
pii anc[MN][H];

void dfs(int n1){
    for(auto [n2, c2] : spanAdjList[n1]){
        dep[n2] = dep[n1] + 1;

        anc[n2][0] = {n1, c2};
        int n3 = n1;
        FOR(k, 1, H){
            if(anc[n3][k-1].fs == -1) break;
            anc[n2][k] = {anc[n3][k-1].fs, min(anc[n3][k-1].sn, anc[n2][k-1].sn)};
            n3 = anc[n3][k-1].fs;
        }

        dfs(n2);
    }
}

int getMn(int a, int b){
    if(dep[a] < dep[b]) swap(a, b);
    int res = INF;
    FORR(k, H-1, 0){
        if(dep[a] - (1<<k) < dep[b]) continue;
        res = min(res, anc[a][k].sn);
        a = anc[a][k].fs;
    }

    if(a == b) return res;

    FORR(k, H-1, 0){
        if(anc[a][k].fs == anc[b][k].fs) continue;
        res = min(res, min(anc[a][k].sn, anc[b][k].sn));
        a = anc[a][k].fs;
        b = anc[b][k].fs;
    }

    res = min(res, min(anc[a][0].sn, anc[b][0].sn));
    return res;
}

void recalc(int t){
    spanTree.clear();
    FR(i, n){
        spanAdjList[i].clear();
        vis[i] = false;
    }

    minPq<pair<int, Edge>> pq;
    pq.push({0, {0, 0, 0}});

    while(!pq.empty()){
        auto [c, e] = pq.top(); pq.pop();
        if(vis[e.n2]) continue;
        vis[e.n2] = true;
        if(e.t) spanAdjList[e.n1].insert({e.n2, e.t}), spanTree.pb(e.t);

        for(Edge e2 : adjList[e.n2]){
            if(!vis[e2.n1]) pq.push({abs(t - e2.t), {e2.t, e.n2, e2.n1}});
        }
    }

    ms(anc, -1);
    dfs(0);

    nextEvent = {INF, -1};
    FR(i, m){
        int a = edges[i].n1, b = edges[i].n2;
        int mn = getMn(a, b);
        if(mn >= edges[i].t) continue;
        int dec = (mn + edges[i].t + 2)/2;
        assert(dec > t);
        nextEvent = min(nextEvent, pii{dec, i});
    }
}


vi perEdge[MN];

void lineCase(){
    //vi mem(3e7, 12345);

    minPq<pii> events;
    FR(i, n-1){
        vi &vec = perEdge[i];
        sort(ALL(vec));
        reverse(ALL(vec));
        if(SZ(vec) >= 2) events.push({(vec[SZ(vec)-1] + vec[SZ(vec)-2])/2 + 1, i});
    }

    while(qi < q){
        int t = queries[qi++];
        while(!events.empty() && events.top().fs < t){
            auto [useless, i] = events.top(); events.pop();
            vi &vec = perEdge[i];
            vec.pop_back();
            if(SZ(vec) >= 2) events.push({(vec[SZ(vec)-1] + vec[SZ(vec)-2])/2 + 1, i});
        }

        ll ans = 0;
        FR(i, n-1) ans += abs(t - perEdge[i].back());
        cout << ans << '\n';
    }

    exit(0);
}

int main(){
    boost();
    cin >> n >> m;
    FR(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        perEdge[a].pb(c);
        adjList[a].pb({c, b, i});
        adjList[b].pb({c, a, i});
        edges[i] = {c, a, b};
    }

    cin >> q;
    FR(i, q) cin >> queries[i];
    //lineCase();
    if(m > 1000 && q > 10) lineCase();

    while(qi < q){
        int t = queries[qi];
        if(nextEvent.fs <= t) recalc(t);
        ll val = 0;
        for(int x : spanTree) val += abs(t - x);
        cout << val << '\n';
        qi++;
    }
}

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