oj.uz

Submission #550730

# Submission time Handle Problem Language Result Execution time Memory
550730 2022-04-18T23:37:57 Z BalintR Reconstruction Project (JOI22_reconstruction) C++17
35 / 100
 5000 ms 21116 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 340 KB Output is correct
2 Correct 1 ms 380 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 380 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 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 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 340 KB Output is correct
17 Correct 1 ms 384 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 380 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 380 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 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 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 340 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 388 KB Output is correct
20 Correct 296 ms 10064 KB Output is correct
21 Correct 198 ms 7064 KB Output is correct
22 Correct 252 ms 8708 KB Output is correct
23 Correct 225 ms 8944 KB Output is correct
24 Correct 247 ms 8840 KB Output is correct
25 Correct 333 ms 8968 KB Output is correct
26 Correct 286 ms 9152 KB Output is correct
27 Correct 306 ms 8980 KB Output is correct
28 Correct 289 ms 8812 KB Output is correct
29 Correct 114 ms 8804 KB Output is correct
30 Correct 300 ms 8812 KB Output is correct
31 Correct 295 ms 8892 KB Output is correct
32 Correct 295 ms 8820 KB Output is correct
33 Correct 296 ms 8664 KB Output is correct
34 Correct 47 ms 7268 KB Output is correct
35 Correct 65 ms 7336 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 384 KB Output is correct
4 Execution timed out 5022 ms 13132 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 340 KB Output is correct
2 Correct 1 ms 380 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 380 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 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 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 340 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 774 ms 19448 KB Output is correct
21 Correct 728 ms 21116 KB Output is correct
22 Correct 710 ms 19708 KB Output is correct
23 Correct 744 ms 19412 KB Output is correct
24 Correct 727 ms 19484 KB Output is correct
25 Correct 719 ms 19260 KB Output is correct
26 Correct 711 ms 19260 KB Output is correct
27 Correct 615 ms 19288 KB Output is correct
28 Correct 684 ms 19320 KB Output is correct
29 Correct 733 ms 19300 KB Output is correct
30 Correct 681 ms 19348 KB Output is correct
31 Correct 678 ms 19512 KB Output is correct
32 Correct 618 ms 20024 KB Output is correct
33 Correct 598 ms 19208 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 380 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 380 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 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 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 340 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 388 KB Output is correct
20 Correct 296 ms 10064 KB Output is correct
21 Correct 198 ms 7064 KB Output is correct
22 Correct 252 ms 8708 KB Output is correct
23 Correct 225 ms 8944 KB Output is correct
24 Correct 247 ms 8840 KB Output is correct
25 Correct 333 ms 8968 KB Output is correct
26 Correct 286 ms 9152 KB Output is correct
27 Correct 306 ms 8980 KB Output is correct
28 Correct 289 ms 8812 KB Output is correct
29 Correct 114 ms 8804 KB Output is correct
30 Correct 300 ms 8812 KB Output is correct
31 Correct 295 ms 8892 KB Output is correct
32 Correct 295 ms 8820 KB Output is correct
33 Correct 296 ms 8664 KB Output is correct
34 Correct 47 ms 7268 KB Output is correct
35 Correct 65 ms 7336 KB Output is correct
36 Execution timed out 5015 ms 9496 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 340 KB Output is correct
2 Correct 1 ms 380 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 380 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 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 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 340 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 388 KB Output is correct
20 Correct 296 ms 10064 KB Output is correct
21 Correct 198 ms 7064 KB Output is correct
22 Correct 252 ms 8708 KB Output is correct
23 Correct 225 ms 8944 KB Output is correct
24 Correct 247 ms 8840 KB Output is correct
25 Correct 333 ms 8968 KB Output is correct
26 Correct 286 ms 9152 KB Output is correct
27 Correct 306 ms 8980 KB Output is correct
28 Correct 289 ms 8812 KB Output is correct
29 Correct 114 ms 8804 KB Output is correct
30 Correct 300 ms 8812 KB Output is correct
31 Correct 295 ms 8892 KB Output is correct
32 Correct 295 ms 8820 KB Output is correct
33 Correct 296 ms 8664 KB Output is correct
34 Correct 47 ms 7268 KB Output is correct
35 Correct 65 ms 7336 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 384 KB Output is correct
39 Execution timed out 5022 ms 13132 KB Time limit exceeded
40 Halted 0 ms 0 KB -