oj.uz

Submission #550729

# Submission time Handle Problem Language Result Execution time Memory
550729 2022-04-18T23:36:28 Z BalintR Reconstruction Project (JOI22_reconstruction) C++17
35 / 100
 5000 ms 26324 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(){
    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;
    if(m > 1000 && q > 10) lineCase();
    FR(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        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];

    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 468 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 384 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 380 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 388 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 384 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 380 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 283 ms 10100 KB Output is correct
21 Correct 229 ms 6944 KB Output is correct
22 Correct 217 ms 8652 KB Output is correct
23 Correct 234 ms 8948 KB Output is correct
24 Correct 274 ms 8972 KB Output is correct
25 Correct 269 ms 9020 KB Output is correct
26 Correct 296 ms 10604 KB Output is correct
27 Correct 300 ms 10112 KB Output is correct
28 Correct 294 ms 10172 KB Output is correct
29 Correct 119 ms 10108 KB Output is correct
30 Correct 276 ms 10340 KB Output is correct
31 Correct 290 ms 10236 KB Output is correct
32 Correct 292 ms 10160 KB Output is correct
33 Correct 279 ms 8660 KB Output is correct
34 Correct 61 ms 8588 KB Output is correct
35 Correct 58 ms 8768 KB Output is correct

Subtask #3
0 / 7.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 Execution timed out 5098 ms 21348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 384 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 380 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 769 ms 26000 KB Output is correct
21 Correct 732 ms 21100 KB Output is correct
22 Correct 759 ms 25544 KB Output is correct
23 Correct 703 ms 26056 KB Output is correct
24 Correct 759 ms 26044 KB Output is correct
25 Correct 729 ms 25940 KB Output is correct
26 Correct 697 ms 25956 KB Output is correct
27 Correct 623 ms 26012 KB Output is correct
28 Correct 693 ms 26196 KB Output is correct
29 Correct 706 ms 26144 KB Output is correct
30 Correct 655 ms 25936 KB Output is correct
31 Correct 652 ms 25808 KB Output is correct
32 Correct 581 ms 26324 KB Output is correct
33 Correct 597 ms 25952 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 384 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 380 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 283 ms 10100 KB Output is correct
21 Correct 229 ms 6944 KB Output is correct
22 Correct 217 ms 8652 KB Output is correct
23 Correct 234 ms 8948 KB Output is correct
24 Correct 274 ms 8972 KB Output is correct
25 Correct 269 ms 9020 KB Output is correct
26 Correct 296 ms 10604 KB Output is correct
27 Correct 300 ms 10112 KB Output is correct
28 Correct 294 ms 10172 KB Output is correct
29 Correct 119 ms 10108 KB Output is correct
30 Correct 276 ms 10340 KB Output is correct
31 Correct 290 ms 10236 KB Output is correct
32 Correct 292 ms 10160 KB Output is correct
33 Correct 279 ms 8660 KB Output is correct
34 Correct 61 ms 8588 KB Output is correct
35 Correct 58 ms 8768 KB Output is correct
36 Execution timed out 5048 ms 10920 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 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 384 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 380 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 380 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 283 ms 10100 KB Output is correct
21 Correct 229 ms 6944 KB Output is correct
22 Correct 217 ms 8652 KB Output is correct
23 Correct 234 ms 8948 KB Output is correct
24 Correct 274 ms 8972 KB Output is correct
25 Correct 269 ms 9020 KB Output is correct
26 Correct 296 ms 10604 KB Output is correct
27 Correct 300 ms 10112 KB Output is correct
28 Correct 294 ms 10172 KB Output is correct
29 Correct 119 ms 10108 KB Output is correct
30 Correct 276 ms 10340 KB Output is correct
31 Correct 290 ms 10236 KB Output is correct
32 Correct 292 ms 10160 KB Output is correct
33 Correct 279 ms 8660 KB Output is correct
34 Correct 61 ms 8588 KB Output is correct
35 Correct 58 ms 8768 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Execution timed out 5098 ms 21348 KB Time limit exceeded
40 Halted 0 ms 0 KB -