Submission #372209

#TimeUsernameProblemLanguageResultExecution timeMemory
372209RohamIzadidoostFactories (JOI14_factories)C++14
0 / 100
29 ms12524 KiB
#include "factories.h" #include<bits/stdc++.h> #define F first #define S second #define mp make_pair #define pb push_back typedef long long ll; using namespace std; const int Max = 5e5 + 10; const int LOG = 20; const ll INF = 1e17 + 10; int n; vector<pair<int , int>> N[Max]; int sttime[Max] , edtime[Max] , ttime , par[Max][LOG] , h[Max]; ll dst[Max]; void DFS(int v , int p = 0) { sttime[v] = ++ttime; for(int lg = 1 ; lg < LOG ; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1]; for(pair<int , int> u : N[v]) if(u.F != p) h[u.F] = h[v] + 1 , par[u.F][0] = v , dst[u.F] = dst[v] + u.S , DFS(u.F , v); edtime[v] = ttime + 1; } int lca(int a , int b) { if(h[a] < h[b]) swap(a , b); for(int lg = LOG ; lg-- ; ) if((h[a] - h[b]) & (1 << lg)) a = par[a][lg]; if(a == b) return a; for(int lg = LOG ; lg-- ; ) if(par[a][lg] != par[b][lg]) a = par[a][lg] , b = par[b][lg]; return par[a][0]; } void Init(int N , int A[] , int B[] , int D[]) { n = N; for(int i = 0 ; i < n - 1 ; i++) ::N[A[i]].pb(mp(B[i] , D[i])) , ::N[B[i]].pb(mp(A[i] , D[i])); DFS(0); } ll DST[Max] , S[Max]; void dfs(vector<int> verts) { int R = 0; S[++R] = verts[0]; for(int i = 1 ; i < verts.size() ; i++) { while(sttime[S[R]] > sttime[verts[i]] || edtime[S[R]] <= sttime[verts[i]]) R--; DST[S[R]] = min(DST[S[R]] , DST[verts[i]] + dst[verts[i]] - dst[S[R]]); DST[verts[i]] = min(DST[verts[i]] , DST[S[R]] + dst[verts[i]] - dst[S[R]]); S[++R] = verts[i]; } } long long Query(int S , int X[] , int T , int Y[]) { vector<pair<int , int>> srt1 , srt2; for(int i = 0 ; i < S ; i++) srt1.pb(mp(sttime[X[i]] , X[i])) , srt2.pb(mp(sttime[X[i]] , X[i])); for(int i = 0 ; i < T ; i++) srt1.pb(mp(sttime[Y[i]] , Y[i])) , srt2.pb(mp(sttime[Y[i]] , Y[i])); sort(srt1.begin() , srt1.end()); for(int i = 0 ; i < srt1.size() - 1 ; i++) { int l = lca(srt1[i].S , srt1[i + 1].S); srt2.pb(mp(sttime[l] , l)); } { int l = lca(srt1[0].S , srt1.back().S); srt2.pb(mp(sttime[l] , l)); } sort(srt2.begin() , srt2.end()); vector<int> verts; for(pair<int , int> v : srt2) verts.pb(v.S) , DST[v.S] = INF; verts.resize(unique(verts.begin() , verts.end()) - verts.begin()); for(int i = 0 ; i < S ; i++) DST[X[i]] = 0; dfs(verts); dfs(verts); ll ans = INF; for(int i = 0 ; i < T ; i++) ans = min(ans , DST[Y[i]]); return ans; }

Compilation message (stderr)

factories.cpp: In function 'void dfs(std::vector<int>)':
factories.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 1 ; i < verts.size() ; i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0 ; i < srt1.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...