Submission #1256172

#TimeUsernameProblemLanguageResultExecution timeMemory
1256172ZeroCoolFactories (JOI14_factories)C++20
33 / 100
8093 ms176604 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #define ar array #define int long long const int N = 5e5 + 20; const int LOG = 20; vector<ar<int,2>> g[N]; int d[N]; int dep[N]; int up[N][LOG]; void chmin(int &x,int y){ x = min(x, y); } void dfs(int x,int p){ up[x][0] = p; for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1]; for(auto [u, w]: g[x]){ if(u == p)continue; d[u] = d[x] + w; dep[u] = dep[x] + 1; dfs(u, x); } } int lca(int a,int b){ if(dep[a] < dep[b])swap(a, b); int k = dep[a] - dep[b]; for(int i = 0;i < LOG;i++){ if((1 << i) & k)a = up[a][i]; } if(a == b)return a; for(int i = LOG - 1;i >= 0;i--){ if(up[a][i] != up[b][i]){ a = up[a][i]; b = up[b][i]; } } return up[a][0]; } int qry(int a, int b){ int l = lca(a, b); return d[a] + d[b] - 2 * d[l]; } bool del[N]; int par[N]; int sz[N]; int dfs1(int x,int p){ sz[x] = 1; for(auto [u, w]: g[x]){ if(u == p || del[u])continue; sz[x] += dfs1(u, x); } return sz[x]; } int C(int x,int p,int s){ for(auto [u, w]: g[x]){ if(u == p || del[u])continue; if(sz[u] > s)return C(u, x, s); } return x; } void cc(int x,int p){ int s = dfs1(x, x); x = C(x, x, s / 2); del[x] = 1; par[x] = p; for(auto [u, w]: g[x]){ if(del[u])continue; cc(u, x); } } int mn[N]; int nn; void Init(signed n, signed A[], signed B[], signed D[]) { nn = n; for(int i = 0;i < n - 1;i++){ g[A[i]].push_back({B[i], D[i]}); g[B[i]].push_back({A[i], D[i]}); } dfs(0, 0); cc(0, -1); // for(int i = 0;i < n;i++)cout<<par[i]<<" "; //cout<<'\n'; // cout<<"what"<<lca(1, 6)<<'\n'; for(int i = 0;i < n;i++)mn[i] = 1e17; //assert(0); } long long Query(signed n, signed X[], signed m, signed Y[]) { set<int> s; for(int i = 0;i < n;i++){ int x = X[i]; //cout<<"AA: "; while(x != -1){ // cout<<x<<" "; s.insert(x); chmin(mn[x], qry(x, X[i])); x = par[x]; } //cout<<'\n'; } // for(int i = 0;i < nn;i++)cout<<mn[i]<<" "; // cout<<'\n'; int ans = 1e17; for(int i = 0;i < m;i++){ int x = Y[i]; // cout<<"AA: "; while(x != -1){ // cout<<x<<" "; chmin(ans, mn[x] + qry(x, Y[i])); x = par[x]; } // cout<<'\n'; } for(auto u: s)mn[u] = 1e17; return ans; } #define int signed

Compilation message (stderr)

factories.cpp:133: warning: "int" redefined
  133 | #define int signed
      | 
factories.cpp:5: note: this is the location of the previous definition
    5 | #define int long long
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...