Submission #934981

#TimeUsernameProblemLanguageResultExecution timeMemory
934981BaizhoFactories (JOI14_factories)C++17
15 / 100
8064 ms199764 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> // #pragma GCC optimize("Ofast,unroll-loops,fast-math") // #pragma GCC target("popcnt") typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; #define sz size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define pb push_back const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6 const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod const long long inf = 5e18; const long double eps = 1e-15L; const int M = 5e5 + 10; ll n, m, par[M + 10], siz[M + 10], up[20][M + 10], col[M + 10]; bool del[M + 10]; long long dis[M + 10], depth[M + 10], wei[M + 10]; vector<pair<int, int> > g[M + 10]; void qfs(int v, int p = 0) { depth[v] = depth[p] + 1; dis[v] = inf; up[0][v] = p; for(int j = 1; j <= 19; j ++) up[j][v] = up[j - 1][up[j - 1][v]]; for(auto to : g[v]) { if(to.ff == p) continue; wei[to.ff] = wei[v] + to.ss; qfs(to.ff, v); } } void dfs_size(int v, int p = -1) { siz[v] = 1; for(auto to : g[v]) { if(to.ff == p || del[to.ff]) continue; dfs_size(to.ff, v); siz[v] += siz[to.ff]; } } int getc(int v, int n, int p = -1) { // cout<<v<<" yolo "<<n<<endl; for(auto to : g[v]) { if(to.ff == p || del[to.ff] || siz[to.ff] <= n / 2) continue; return getc(to.ff, n, v); } // cout<<v<<endl; return v; } void decomp(int v, int p = 0) { dfs_size(v); // cout<<v<<" "<<p<<endl; int c = getc(v, siz[v]); // cout<<c<<" "<<endl; par[c] = p; del[c] = 1; for(auto to : g[c]) { if(del[to.ff]) continue; decomp(to.ff, c); } } int lca(int u, int v) { if(depth[u] < depth[v]) swap(u, v); // cout<<u<<" "<<v<<" "<<" "<<depth[u]<<" "<<depth[v]<<" "; int dif = depth[u] - depth[v]; for(int j = 19; j >= 0; j --) { if(dif & (1 << j)) u = up[j][u]; } // cout<<u<<" "; if(u == v) return u; for(int j = 19; j >= 0; j --) { if(up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; } } // cout<<up[0][u]<<"\n"; return up[0][u]; } long long dist(int u, int v) { // cout<<u<<" "<<v<<" "<<depth[u] + depth[v] - depth[lca(u, v)] * 2<<"\n"; return wei[u] + wei[v] - wei[lca(u, v)] * 2; } void add(long long v) { long long x = v; while(v > 0) { // cout<<v<<" her1 "<<endl; // cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n"<<endl; dis[v] = min(dis[v], dist(v, x)); v = par[v]; } } void erase(long long v) { long long x = v; while(v > 0) { // cout<<v<<" her2 "<<endl; // cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n"; dis[v] = inf; v = par[v]; } } long long get(int v) { long long ans = inf, x = v; while(v > 0) { // cout<<v<<" her3 "<<endl; ans = min(ans, dist(v, x) + dis[v]); v = par[v]; } return ans; } void Init(int N, int A[], int B[], int D[]) { // cout<<N<<endl; n = N; // cout<<"YOLO "<<endl; for(int i = 0; i <= n - 2; i ++) { A[i] ++; B[i] ++; g[A[i]].pb({B[i], D[i]}); g[B[i]].pb({A[i], D[i]}); } qfs(1); decomp(1); // for(int i = 1; i <= n; i ++) cout<<par[i]<<" "; // cout<<"\n"; } long long Query(int S, int X[], int T, int Y[]) { for(int i = 0; i < S; i ++) { X[i] ++; add(X[i]); } long long ans = inf; for(int i = 0; i < T; i ++) { Y[i] ++; ans = min(ans, get(Y[i])); } // cout<<"YOLO "<<endl; for(int i = 0; i < S; i ++) { erase(X[i]); } return ans; }

Compilation message (stderr)

factories.cpp: In function 'void erase(long long int)':
factories.cpp:114:12: warning: unused variable 'x' [-Wunused-variable]
  114 |  long long x = v;
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...