Submission #529869

#	Time	Username	Problem	Language	Result	Execution time	Memory
529869		Lobo	Factories (JOI14_factories)	C++17	15 / 100	8074 ms	171332 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 500050

int n, szfc[maxn], block[maxn], h[maxn], pc[maxn], tin[maxn], tout[maxn];
pair<int,int> mnr[2*maxn][25], mnl[2*maxn][25];
int d[maxn], mn[maxn];
vector<int> vfc;
vector<pair<int,int>> g[maxn], el;

void dfsfc(int u, int ant) {
    szfc[u] = 1;
    vfc.pb(u);

    for(auto V : g[u]) {
        int v = V.fr;
        if(v == ant || block[v]) continue;
        dfsfc(v,u);
        szfc[u]+= szfc[v];
    }
}

int p[maxn][23];
void dfslca(int u, int ant) {
    p[u][0] = ant;
    for(int i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }
 
    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == ant) continue;
        h[v] = h[u]+1;
        d[v] = d[u]+w;
        dfslca(v,u);
    }
}
 
int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);
 
    for(int i = 20; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }
 
    if(u == v) return u;
 
    for(int i = 20; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }
 
    return p[u][0];
}

int fcent(int beg) {
    vfc.clear();
    dfsfc(beg,beg);
    int cent = beg;

    for(auto u : vfc) {
        bool ok = true;
        if(szfc[beg]-szfc[u] > szfc[beg]/2) ok = false;

        for(auto V : g[u]) {
            int v = V.fr;
            if(block[v]) continue;
            if(szfc[v] > szfc[u]) continue;
            if(szfc[v] > szfc[beg]/2) ok = false;
        }

        if(ok) cent = u;
    }

    block[cent] = 1;
    for(auto V : g[cent]) {
        int v = V.fr;
        if(block[v]) continue;
        pc[fcent(v)] = cent;
    }

    return cent;
}

int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    int ans = inf;
    for(int i = 0; i < S; i++) {
        int v = X[i];
        while(v != -1) {
            int dis = d[X[i]]+d[v]-2*d[lca(X[i],v)];
            mn[v] = min(mn[v],dis);
            v = pc[v];
        }
    }
 
    for(int i = 0; i < T; i++) {
        int v = Y[i];
        while(v != -1) {
            int dis = d[Y[i]]+d[v]-2*d[lca(Y[i],v)];
            ans = min(ans, mn[v]+dis);
            v = pc[v];
        }
    }
 
    for(int i = 0; i < S; i++) {
        int v = X[i];
        while(v != -1) {
            mn[v] = inf;
            v = pc[v];
        }
    }
 
    return ans;
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    n = N;
    for(int i = 0; i < n-1; i++) {
        g[A[i]].pb(mp(B[i],D[i]));
        g[B[i]].pb(mp(A[i],D[i]));
    }

    for(int i = 0; i < n; i++) {
        pc[i] = -1;
        mn[i] = inf;
    }
    fcent(0);
    dfslca(0,0);
    for(int i = 0; i < el.size(); i++) {
        mnr[i][0] = el[i];
    }
    for(int j = 1; j <= 21; j++) {
        for(int i = 0; i < el.size(); i++) {
            mnr[i][j] = min(mnr[i][j-1],mnr[min((int) el.size()-1, i+(1<<(j-1)))][j-1]);  
        }
    }

    for(int i = 0; i < el.size(); i++) {
        mnl[i][0] = el[i];
    }
    for(int j = 1; j <= 21; j++) {
        for(int i = 0; i < el.size(); i++) {
            mnl[i][j] = min(mnl[i][j-1],mnl[max(0LL, i-(1<<(j-1)))][j-1]);  
        }
    }
}

/*
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int32_t N, Q; cin >> N >> Q;
    int32_t A[N-1], B[N-1], D[N-1];
    for(int i = 0; i < N-1; i++) {
        cin >> A[i] >> B[i] >> D[i];
    }

    Init(N,A,B,D);

    while(Q--) {
        int32_t S, T; cin >> S >> T;
        int32_t X[S], Y[T];
        for(int i = 0; i < S; i++) cin >> X[i];
        for(int i = 0; i < T; i++) cin >> Y[i];

        cout << Query(S,X,T,Y) << endl;
    }


}
*/

Compilation message (stderr)

factories.cpp: In function 'void Init(int32_t, int32_t*, int32_t*, int32_t*)':
factories.cpp:147:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:151:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~
factories.cpp:156:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:160:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67