Submission #708386

#	Time	Username	Problem	Language	Result	Execution time	Memory
708386		Dan4Life	Factories (JOI14_factories)	C++17	0 / 100	308 ms	524288 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
using ll = long long;
const int mxN = (int)5e5+10;
const int mxLg = (int)20;
const ll LINF = (ll)4e18;
int n, sub[mxN], par[mxN], vis[mxN];
ll D[mxN], depth[mxN], best[mxN];
unordered_map<int,ll> ddis[mxN];
int jmp[mxLg][mxN];
vector<pair<int,ll>> adj[mxN];

int fcentroid(int s, int p, int n){
    for(auto x : adj[s]){
        int u = x.fi;
        if(u!=p and sub[u]>n/2 and !vis[u])
            return fcentroid(u,s,n);
    }
    return s;
}

int dfs(int s, int p, bool general){
    sub[s]=1;
    if(general){
        jmp[0][s]=p;
        if(p!=-1) depth[s] = depth[p]+1;
    }
    for(int i=0; auto x : adj[s]){
        int u = x.fi, w = x.se;
        if(u==p) continue;
        if(general) D[u] = D[s]+w;
        if(!vis[u]) sub[s]+=dfs(u,s,general);
        if(sub[u]>sub[adj[s][0].fi])
            swap(adj[s][0], adj[s][u]); i++;
    }
    return sub[s];
}

void centroid_decomp(int s, int p){
    int n = dfs(s,p,0);
    int centroid = fcentroid(s,p,n);
    vis[centroid] = 1; par[centroid] = p;
    for(auto x : adj[centroid]){
        int u = x.fi;
        if(u!=p and !vis[u])
            centroid_decomp(u,centroid);
    }
}

int getPath(int x, int k){
    for(int i = 0; i < mxLg; i++)
        if(k&(1<<i) and x!=-1) x=jmp[i][x];
    return x;
}

int lca(int a, int b){
    if(a==b) return a;
    if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
    if(depth[a]>depth[b]) swap(a,b);
    b = getPath(b,depth[b]-depth[a]);
    for(int i = mxLg-1; i >= 0; i--)
        if(jmp[i][a]!=-1 and jmp[i][b]!=-1 and jmp[i][a]!=jmp[i][b])
            a=jmp[i][a], b = jmp[i][b];
    return lca(a,b);
}

ll dis(int a, int b){
    return D[a]+D[b]-2*D[lca(a,b)];
}

void Init(int N, int a[], int b[], int d[]) {
    n = N; memset(jmp,-1,sizeof(jmp));
    memset(par,-1,sizeof(par));
    memset(best,-1,sizeof(best));
    for(int i = 0; i < n-1; i++){
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
    dfs(0,-1,1); centroid_decomp(0,-1);
    for(int i = 1; i < mxLg; i++)
        for(int j = 0; j < n; j++)
            if(jmp[i-1][j]!=-1)
                jmp[i][j] = jmp[i-1][jmp[i-1][j]];
    for(int i = 0; i < n; i++){
        int x = i;
        while(x!=-1){
            ddis[x][i]=dis(x,i);
            x = par[x];
        }
    }
}

ll Query(int s, int x[], int t, int y[]) {
    vector<int> rem; rem.clear();
    for(int i = 0; i < s; i++){
        int a = x[i];
        while(a!=-1){
            ll DD = ddis[a][x[i]];
            if(best[a]==-1) best[a]=DD;
            else best[a]=min(best[a],DD);
            rem.pb(a), a = par[a];
        }
    }
    ll ans = LINF;
    for(int i = 0; i < t; i++){
        int x = y[i];
        while(x!=-1){
            if(best[x]!=-1) ans = min(ans, ddis[x][y[i]]+best[x]);
            x=par[x];
        }
    }
    for(auto u : rem) best[u]=-1;
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'int dfs(int, int, bool)':
factories.cpp:32:18: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   32 |     for(int i=0; auto x : adj[s]){
      |                  ^~~~
factories.cpp:37:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |         if(sub[u]>sub[adj[s][0].fi])
      |         ^~
factories.cpp:38:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |             swap(adj[s][0], adj[s][u]); i++;
      |                                         ^

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