Submission #807289

#TimeUsernameProblemLanguageResultExecution timeMemory
807289hoangnghiepFactories (JOI14_factories)C++14
Compilation error
0 ms0 KiB
#include "factories.h" #include <stdio.h> #include <stdlib.h> #include<bits/stdc++.h> #define ll long long #define pii pair<int,ll> #define f first #define s second //#define multipletest using namespace std; const int LIM=5e5; const ll INF=1e18; const string name="template"; #define MAX_N 500000 #define MAX_Q 100000 #define MAX_SUM_ST 1000000 #define MAX_VALUE 1000000000 static int N, Q; static int A[MAX_N], B[MAX_N], D[MAX_N]; static int S[MAX_N]; static int T[MAX_N]; static int X[MAX_SUM_ST]; static int Y[MAX_SUM_ST]; static int Qx[MAX_N]; static int Qy[MAX_N]; int n,m; vector<pii> adj[LIM+5],adj_vt[LIM+5]; int time_dfs=0; pii euler_tour[2*LIM+5],sparse_table[20][2*LIM+5]; int tin[LIM+5],tout[LIM+5],h[LIM+5]; ll dist_X[LIM+5],dist_Y[LIM+5],dist[LIM+5]; vector<int> List; int color[LIM+5]; vector<int> st; void dfs(int u,int parent,int depth){ h[u] = depth; tin[u] = time_dfs; euler_tour[time_dfs++] = {depth,u}; for(auto v:adj[u]){ if(v.f==parent) continue; dist[v.f] = dist[u] + v.s; dfs(v.f,u,depth + 1); euler_tour[time_dfs++] = {depth,u}; } tout[u] = time_dfs; } int lca(int u,int v){ if(tin[u]>tin[v]){ swap(u,v); } int bt = 31 - __builtin_clz(tin[v]-tin[u]+1); pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]); return mn.s; } ll Dist(int u,int v){ int LCA = lca(u,v); return dist[u] + dist[v]- 2*dist[LCA]; } bool cmp(int a,int b){ return tin[a]<tin[b]; } bool isSubtree(int u,int v) { return tin[u]<=tin[v] && tin[v]<=tout[u]; } void dfs_to_find_sol(int u,int parent){ for(auto v:adj_vt[u]){ if(v.f==parent) continue; dfs_to_find_sol(v.f,u); dist_X[u] = min(dist_X[u],dist_X[v.f] + v.s); dist_Y[u] = min(dist_Y[u],dist_Y[v.f] + v.s); } } void Init(int N, int A[], int B[], int D[]){ n=N; for(int i=0;i<n-1;++i){ A[i]++; B[i]++; } for(int i=0;i<n-1;++i){ adj[A[i]].push_back({B[i],D[i]}); adj[B[i]].push_back({A[i],D[i]}); } for(int i=1;i<=n;++i){ dist_X[i]=INF; dist_Y[i]=INF; dist[i]=0; color[i] = -1; } dfs(1,0,0); for(int i=0;i<time_dfs;++i){ sparse_table[0][i] = euler_tour[i]; } for(int i=1;i<20;++i){ for(int j=0;j+(1<<i)-1<time_dfs;++j){ sparse_table[i][j] = min(sparse_table[i-1][j],sparse_table[i-1][j + (1<<(i-1))]); } } } long long Query(int S, int X[], int T, int Y[]){ for(auto x:List){ color[x] = -1; adj_vt[x].clear(); dist_X[x]=dist_Y[x]=INF; } List.clear(); st.clear(); for(int i=0;i<S;++i){ List.push_back(++X[i]); color[X[i]] = 0; dist_X[X[i]]=0; dist_Y[X[i]]=INF; } for(int i=0;i<T;++i){ List.push_back(++Y[i]); if(color[Y[i]]==0){ return 0; } color[Y[i]]=1; dist_X[Y[i]]=INF; dist_Y[Y[i]]=0; } sort(List.begin(),List.end(),cmp); for(int i=1;i<S+T;++i){ int LCA = lca(List[i-1],List[i]); if(color[LCA]==-1){ dist_X[LCA] = dist_Y[LCA] = INF; } List.push_back(LCA); } int root; sort(List.begin(),List.end(),cmp); List.erase(unique(List.begin(),List.end()),List.end()); for(int i=0;i<List.size();++i){ int u = List[i]; while(st.size()>=2 && !isSubtree(st.back(),u)){ int x = st[st.size()-2]; int y= st.back(); ll w=Dist(x,y); adj_vt[x].push_back({y,w}); adj_vt[y].push_back({x,w}); root=x; st.pop_back(); } st.push_back(u); } while(st.size()>=2){ int x = st[st.size()-2]; int y= st.back(); ll w=Dist(x,y); adj_vt[x].push_back({y,w}); adj_vt[y].push_back({x,w}); root=x; st.pop_back(); } dfs_to_find_sol(root,0); ll ans=INF; for(auto x:List){ ans = min(ans,dist_X[x] + dist_Y[x]); } return ans; } int main() { freopen("sample-in-01.txt","r",stdin); int i, j, k; int STop, TTop; if (2 != scanf("%d%d", &N, &Q)) { fprintf(stderr, "error: cannot read N and Q.\n"); exit(1); } if (!(2 <= N && N <= MAX_N)) { fprintf(stderr, "error: N is out of bounds.\n"); exit(1); } if (!(1 <= Q && Q <= MAX_Q)) { fprintf(stderr, "error: Q is out of bounds.\n"); exit(1); } for (i = 0; i < N - 1; ++i) { if (1 != scanf("%d", &A[i])) { fprintf(stderr, "error: cannot read A[%d].\n", i); exit(1); } if (!(0 <= A[i] && A[i] <= N - 1)) { fprintf(stderr, "error: A[%d] is out of bounds.\n", i); exit(1); } if (1 != scanf("%d", &B[i])) { fprintf(stderr, "error: cannot read B[%d].\n", i); exit(1); } if (!(0 <= B[i] && B[i] <= N - 1)) { fprintf(stderr, "error: B[%d] is out of bounds.\n", i); exit(1); } if (A[i] == B[i]) { fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i); exit(1); } if (1 != scanf("%d", &D[i])) { fprintf(stderr, "error: cannot read D[%d].\n", i); exit(1); } if (!(1 <= D[i] && D[i] <= MAX_VALUE)) { fprintf(stderr, "error: D[%d] is out of bounds.\n", i); exit(1); } } STop = 0; TTop = 0; for (j = 0; j < Q; ++j) { if (2 != scanf("%d%d", &S[j], &T[j])) { fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j); exit(1); } if(STop + S[j] > MAX_SUM_ST) { fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j); exit(1); } if(TTop + T[j] > MAX_SUM_ST) { fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j); exit(1); } for (k = 0; k < S[j]; ++k, ++STop) { if (1 != scanf("%d", &X[STop])) { fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k); exit(1); } if (!(0 <= X[STop] && X[STop] <= N - 1)) { fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k); exit(1); } } for (k = 0; k < T[j]; ++k, ++TTop) { if (1 != scanf("%d", &Y[TTop])) { fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k); exit(1); } if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) { fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k); exit(1); } } } STop = 0; TTop = 0; Init(N, A, B, D); for (j = 0; j < Q; ++j) { for (k = 0; k < S[j]; k++) { Qx[k] = X[STop++]; } for (k = 0; k < T[j]; k++) { Qy[k] = Y[TTop++]; } printf("%lld\n", Query(S[j], Qx, T[j], Qy)); } return 0; }

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:151:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for(int i=0;i<List.size();++i){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int main()':
factories.cpp:181:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |   freopen("sample-in-01.txt","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:173:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  173 |  dfs_to_find_sol(root,0);
      |  ~~~~~~~~~~~~~~~^~~~~~~~
/usr/bin/ld: /tmp/ccJ5nkEq.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHVaTbs.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status