oj.uz

Submission #550739

# Submission time Handle Problem Language Result Execution time Memory
550739 2022-04-18T23:46:22 Z BalintR Reconstruction Project (JOI22_reconstruction) C++17
35 / 100
 1040 ms 138148 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 302 ms 9364 KB Output is correct
21 Correct 210 ms 7696 KB Output is correct
22 Correct 221 ms 9400 KB Output is correct
23 Correct 246 ms 9476 KB Output is correct
24 Correct 247 ms 9372 KB Output is correct
25 Correct 293 ms 9520 KB Output is correct
26 Correct 279 ms 9500 KB Output is correct
27 Correct 319 ms 9320 KB Output is correct
28 Correct 273 ms 9204 KB Output is correct
29 Correct 109 ms 9160 KB Output is correct
30 Correct 280 ms 9172 KB Output is correct
31 Correct 278 ms 9272 KB Output is correct
32 Correct 306 ms 9344 KB Output is correct
33 Correct 275 ms 9220 KB Output is correct
34 Correct 49 ms 7644 KB Output is correct
35 Correct 55 ms 7636 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1040 ms 138148 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 770 ms 16632 KB Output is correct
21 Correct 743 ms 16780 KB Output is correct
22 Correct 704 ms 16728 KB Output is correct
23 Correct 718 ms 16848 KB Output is correct
24 Correct 705 ms 16640 KB Output is correct
25 Correct 715 ms 16588 KB Output is correct
26 Correct 719 ms 16748 KB Output is correct
27 Correct 629 ms 16972 KB Output is correct
28 Correct 735 ms 16572 KB Output is correct
29 Correct 780 ms 16724 KB Output is correct
30 Correct 657 ms 16608 KB Output is correct
31 Correct 693 ms 16712 KB Output is correct
32 Correct 607 ms 17144 KB Output is correct
33 Correct 583 ms 16412 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 302 ms 9364 KB Output is correct
21 Correct 210 ms 7696 KB Output is correct
22 Correct 221 ms 9400 KB Output is correct
23 Correct 246 ms 9476 KB Output is correct
24 Correct 247 ms 9372 KB Output is correct
25 Correct 293 ms 9520 KB Output is correct
26 Correct 279 ms 9500 KB Output is correct
27 Correct 319 ms 9320 KB Output is correct
28 Correct 273 ms 9204 KB Output is correct
29 Correct 109 ms 9160 KB Output is correct
30 Correct 280 ms 9172 KB Output is correct
31 Correct 278 ms 9272 KB Output is correct
32 Correct 306 ms 9344 KB Output is correct
33 Correct 275 ms 9220 KB Output is correct
34 Correct 49 ms 7644 KB Output is correct
35 Correct 55 ms 7636 KB Output is correct
36 Incorrect 104 ms 123204 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 302 ms 9364 KB Output is correct
21 Correct 210 ms 7696 KB Output is correct
22 Correct 221 ms 9400 KB Output is correct
23 Correct 246 ms 9476 KB Output is correct
24 Correct 247 ms 9372 KB Output is correct
25 Correct 293 ms 9520 KB Output is correct
26 Correct 279 ms 9500 KB Output is correct
27 Correct 319 ms 9320 KB Output is correct
28 Correct 273 ms 9204 KB Output is correct
29 Correct 109 ms 9160 KB Output is correct
30 Correct 280 ms 9172 KB Output is correct
31 Correct 278 ms 9272 KB Output is correct
32 Correct 306 ms 9344 KB Output is correct
33 Correct 275 ms 9220 KB Output is correct
34 Correct 49 ms 7644 KB Output is correct
35 Correct 55 ms 7636 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Incorrect 1040 ms 138148 KB Output isn't correct
40 Halted 0 ms 0 KB -