#include "factories.h"
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
vector<int> g[MAXN],gt[MAXN];
vector<long long> c[MAXN],d[MAXN];
int p[MAXN],n,sz,cn,in[MAXN],gl,arr[MAXN];
long long be[MAXN];
map <pair<int,int>,long long> m;
bool vc[MAXN];
int dfssize(int s,int f)
{
int x=1;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) x+=dfssize(g[s][i],s);
return x;
}
int dfsc(int s,int f)
{
int x=1;
bool ce=true;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]])
{
int a=dfsc(g[s][i],s);
if(a>sz/2) ce=false;
x+=a;
}
if(sz-x>sz/2) ce=false;
if(ce) cn=s;
return x;
}
/*void dfst(int s)
{
in[s]=gl++;
for(int i=0;i<gt[s].size();i++) dfst(gt[s][i]);
arr[s]=gl-in[s];
}*/
void dfs(int s,int f,long long dist,int po)
{
if(in[s]<in[po]) return;
m[make_pair(po,s)]=dist;//d[po][in[s]-in[po]]=dist;
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,dist+c[s][i],po);
}
void centrodecomp(int s,int f)
{
sz=dfssize(s,-1);
dfsc(s,-1);
p[cn]=f;
vc[cn]=true;
int tmp=cn;
for(int i=0;i<g[tmp].size();i++) if(!vc[g[tmp][i]]) centrodecomp(g[tmp][i],tmp);
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
int root;
for(int i=0;i<n-1;i++) {g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); c[A[i]].push_back(D[i]); c[B[i]].push_back(D[i]);}
centrodecomp(0,-1);
for(int i=0;i<n;i++) {if(p[i]!=-1) gt[p[i]].push_back(i); else root=i;}
//dfst(root);
for(int i=0;i<n;i++) for(int j=0;j<arr[i];j++) d[i].push_back(0);
for(int i=0;i<n;i++) dfs(i,-1,0,i);
fill(be,be+MAXN,1000000000000000000LL);
}
long long Query(int S, int X[], int T, int Y[])
{
int s=S,t=T;
long long sk=1000000000000000000LL;
for(int i=0;i<s;i++)
{
int a=X[i];
while(a!=-1) {be[a]=min(be[a], m[make_pair(a,X[i])]/*d[a][in[X[i]]-in[a]]*/); a=p[a];}
}
for(int i=0;i<t;i++)
{
int a=Y[i];
while(a!=-1) {sk=min(sk,m[make_pair(a,Y[i])]/*d[a][in[Y[i]]-in[a]]*/+be[a]); a=p[a];}
}
for(int i=0;i<s;i++)
{
int a=X[i];
while(a!=-1) {be[a]=1000000000000000000LL; a=p[a];}
}
return sk;
}
Compilation message
factories.cpp: In function 'int dfssize(int, int)':
factories.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) x+=dfssize(g[s][i],s);
~^~~~~~~~~~~~
factories.cpp: In function 'int dfsc(int, int)':
factories.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]])
~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(int, int, long long int, int)':
factories.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,dist+c[s][i],po);
~^~~~~~~~~~~~
factories.cpp: In function 'void centrodecomp(int, int)':
factories.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[tmp].size();i++) if(!vc[g[tmp][i]]) centrodecomp(g[tmp][i],tmp);
~^~~~~~~~~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:55:6: warning: variable 'root' set but not used [-Wunused-but-set-variable]
int root;
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
225 ms |
67448 KB |
Output is correct |
| 2 |
Execution timed out |
6166 ms |
524288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
133 ms |
524288 KB |
Output is correct |
| 2 |
Execution timed out |
6045 ms |
524288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6038 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
