oj.uz

Submission #550734

# Submission time Handle Problem Language Result Execution time Memory
550734 2022-04-18T23:41:44 Z BalintR Reconstruction Project (JOI22_reconstruction) C++17
35 / 100
 812 ms 17692 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);
    FR(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        perEdge[a].pb(c);
    }

    minPq<pii> events;
    FR(i, n){
        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.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) 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;
    if(m > 1000 && q > 10) lineCase();
    FR(i, q) cin >> queries[i];

    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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 307 ms 9856 KB Output is correct
21 Correct 210 ms 7792 KB Output is correct
22 Correct 226 ms 9340 KB Output is correct
23 Correct 241 ms 9488 KB Output is correct
24 Correct 262 ms 9576 KB Output is correct
25 Correct 274 ms 9648 KB Output is correct
26 Correct 295 ms 10212 KB Output is correct
27 Correct 286 ms 10136 KB Output is correct
28 Correct 288 ms 10020 KB Output is correct
29 Correct 118 ms 9928 KB Output is correct
30 Correct 288 ms 9952 KB Output is correct
31 Correct 301 ms 9924 KB Output is correct
32 Correct 278 ms 10196 KB Output is correct
33 Correct 303 ms 9228 KB Output is correct
34 Correct 45 ms 8436 KB Output is correct
35 Correct 53 ms 8404 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Runtime error 42 ms 11976 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 714 ms 17236 KB Output is correct
21 Correct 682 ms 17084 KB Output is correct
22 Correct 692 ms 17296 KB Output is correct
23 Correct 705 ms 17152 KB Output is correct
24 Correct 689 ms 17156 KB Output is correct
25 Correct 695 ms 17204 KB Output is correct
26 Correct 692 ms 17324 KB Output is correct
27 Correct 584 ms 17356 KB Output is correct
28 Correct 768 ms 17076 KB Output is correct
29 Correct 749 ms 17172 KB Output is correct
30 Correct 730 ms 17312 KB Output is correct
31 Correct 812 ms 17108 KB Output is correct
32 Correct 664 ms 17692 KB Output is correct
33 Correct 643 ms 16996 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 307 ms 9856 KB Output is correct
21 Correct 210 ms 7792 KB Output is correct
22 Correct 226 ms 9340 KB Output is correct
23 Correct 241 ms 9488 KB Output is correct
24 Correct 262 ms 9576 KB Output is correct
25 Correct 274 ms 9648 KB Output is correct
26 Correct 295 ms 10212 KB Output is correct
27 Correct 286 ms 10136 KB Output is correct
28 Correct 288 ms 10020 KB Output is correct
29 Correct 118 ms 9928 KB Output is correct
30 Correct 288 ms 9952 KB Output is correct
31 Correct 301 ms 9924 KB Output is correct
32 Correct 278 ms 10196 KB Output is correct
33 Correct 303 ms 9228 KB Output is correct
34 Correct 45 ms 8436 KB Output is correct
35 Correct 53 ms 8404 KB Output is correct
36 Runtime error 33 ms 11176 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 307 ms 9856 KB Output is correct
21 Correct 210 ms 7792 KB Output is correct
22 Correct 226 ms 9340 KB Output is correct
23 Correct 241 ms 9488 KB Output is correct
24 Correct 262 ms 9576 KB Output is correct
25 Correct 274 ms 9648 KB Output is correct
26 Correct 295 ms 10212 KB Output is correct
27 Correct 286 ms 10136 KB Output is correct
28 Correct 288 ms 10020 KB Output is correct
29 Correct 118 ms 9928 KB Output is correct
30 Correct 288 ms 9952 KB Output is correct
31 Correct 301 ms 9924 KB Output is correct
32 Correct 278 ms 10196 KB Output is correct
33 Correct 303 ms 9228 KB Output is correct
34 Correct 45 ms 8436 KB Output is correct
35 Correct 53 ms 8404 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Runtime error 42 ms 11976 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -