oj.uz

Submission #660343

# Submission time Handle Problem Language Result Execution time Memory
660343 2022-11-21T17:13:42 Z rafatoa Factories (JOI14_factories) C++17
0 / 100
 6 ms 1380 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")

#define F first
// #define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define double ld
// #define int long long
const long long INF = 4e18;

int n;
vector<vpi> adj;
vector<long long> d, dc, sub, par, best, vis, tin, eul;
vvi st;
vb del;

int tt = 0;

int lg2(int x){
    return 63-__builtin_clzll(x);
}

int cmp(int a, int b){
    return (d[a] < d[b] ? a : b);
}

int lca(int a, int b){
    if(tin[a] > tin[b]) swap(a, b);
    int len = tin[b]-tin[a]+1, lg = lg2(len);
    return cmp(st[tin[a]][lg], st[tin[b]-(1LL<<lg)+1][lg]);
}

long long dist(int a, int b){
    return dc[a]+dc[b]-2*dc[lca(a, b)];
}

void build(){
    d = dc = sub = par = vis = best = tin = vector<long long>(n+1);
    st = vvi(n+1, vi(21));
    del = vb(n+1);

    int time = 0;
    function<void(int, int)> dfs0 = [&](int s, int e){
        tin[s] = time;
        eul.pb(s); time++;
        for(auto [u, c]:adj[s]){
            if(u == e) continue;
            d[u] = d[s]+1;
            dc[u] = dc[s]+c;
            dfs0(u, s);
            eul.pb(s); time++;
        }
    };
    dfs0(1, 0);

    assert(eul.size() == 2*n-1);
    for(int i=0; i<2*n-1; i++) st[i][0] = eul[i];
    for(int j=1; j<=20; j++)
    for(int i=0; i+(1LL<<j)-1<2*n-1; i++)
        st[i][j] = cmp(st[i][j-1], st[i+(1LL<<(j-1))][j-1]);

    //START_CENTROID

    function<void(int, int)> dfs_sub = [&](int s, int e){
        sub[s] = 1;
        for(auto [u, c]:adj[s]){
            if(u == e || del[u]) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };

    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto [u, c]:adj[s])
            if(u != e && !del[u] && sub[u] > sz/2) return centroid(u, s, sz);
        return s;
    };

    function<void(int, int)> decompose = [&](int s, int p){
        dfs_sub(s, 0);
        int C = centroid(s, 0, sub[s]);
        par[C] = p;

        del[C] = 1;
        for(auto [u, c]:adj[C])
            if(!del[u]) decompose(u, C);
    };
    decompose(1, -1);

    //END_CENTROID
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    adj = vector<vpi>(n+1);
    for(int i=0; i<n-1; i++){
        adj[A[i]+1].pb({B[i]+1, D[i]});
        adj[B[i]+1].pb({A[i]+1, D[i]});
    }

    build();
}

long long Query(int S, int X[], int T, int Y[]){
    tt++;
    long long ans = INF;
    
    for(int i=0; i<T; i++){
        Y[i]++;
        int curr = Y[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], dist(curr, Y[i]));
            curr = par[curr];
        }
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+dist(curr, X[i]));
            curr = par[curr];
        }
    }

    return ans;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from factories.cpp:1:
factories.cpp: In function 'void build()':
factories.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     assert(eul.size() == 2*n-1);
      |            ~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1380 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1380 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -