Submission #491720

#	Time	Username	Problem	Language	Result	Execution time	Memory
491720		truc12a2cvp	Factories (JOI14_factories)	C++14	100 / 100	6214 ms	405984 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> II;
const int N = 5e5 + 3;
const int logN = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int n, child[N], a[N], b[N], d[N], q, f[N][logN], depth[N], x[N], y[N], s, t;
bool ers[N];
vector<II> g[N], par[N];
ll dist[N], root_dis[N];

void Dfs(int u = 1, int p = 0, int di = 0){
       depth[u] = depth[p] + 1;
       root_dis[u] = root_dis[p] + di;
       f[u][0] = p;
       for(int i = 1; i < logN; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
       for(auto x : g[u]){
              int v = x.second, uv = x.first;
              if(v == p) continue;
              Dfs(v, u, uv);
       }
}

int lca(int u, int v) {
       if(depth[u] < depth[v]) swap(u, v);
       for(int i = logN - 1; i >= 0; i --){
              if(depth[f[u][i]] >= depth[v]) u = f[u][i];
       }
       if(u == v) return u;
       for(int i = logN - 1; i >= 0; i --){
              if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
       }
       return f[u][0];
}

inline ll get_dist(int u, int v){
       return root_dis[u] + root_dis[v] - 2 * root_dis[lca(u, v)];
}

int dfs(int u, int p = 0){
       child[u] = 1;
       for(auto x : g[u]){
              int v = x.second;
              if(v != p && !ers[v]) child[u] += dfs(v, u);
       }
       return child[u];
}

int get_centroid(int u, int sz, int p = 0){
       for(auto x : g[u]){
              int v = x.second;
              if(!ers[v] && v != p && child[v] * 2 > sz) return get_centroid(v, sz, u);
       }
       return u;
}

void centroid(int u = 1, int p = 0){
       int cen = get_centroid(u, dfs(u));
       for(auto x : par[p]) par[cen].push_back(II(x.first, get_dist(cen, x.first)));
       par[cen].push_back(II(cen, 0));
       ers[cen] = true;
       for(auto x : g[cen]){
              int v = x.second;
              if(!ers[v]) centroid(v, cen);
       }
}

void Init(int N, int A[], int B[], int D[]){
       n = N;
       for(int i = 1; i <= n; i ++) dist[i] = INF, g[i].clear();
       for(int i = 0; i <= n - 2; i ++){
              A[i] ++;
              B[i] ++;
              g[A[i]].push_back(II(D[i], B[i]));
              g[B[i]].push_back(II(D[i], A[i]));
       }
       Dfs();
       centroid();
}

ll Query(int S, int X[], int T, int Y[]){
       for(int i = 0; i < S; i ++){
              X[i] ++;
              for(auto x : par[X[i]]) dist[x.first] = min(dist[x.first], x.second);
       }

       ll ans = INF;
       for(int i = 0; i < T; i ++){
              Y[i] ++;
              for(auto x : par[Y[i]]) ans = min(ans, dist[x.first] + x.second);
       }
       for(int i = 0; i < S; i ++){
              for(auto x : par[X[i]]) dist[x.first] = INF;
       }
       return ans;
}

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