#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
int n;
vector<pli> lis[500100];
int sz[500100];
int num[500100], en[500100], ord[500100], stp[500100];
ll dep[22][500100];
vector<int> st[500100];
bool dead[500100];
int idfs(int here, int p) {
int i;
sz[here] = 1;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (dead[there]||there==p) continue;
sz[here] += idfs(there,here);
}
return sz[here];
}
int cdfs(int here, int p, int asz) {
int i, maxi = -1, t = -1;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (dead[there]||there==p) continue;
if (maxi<sz[there]) {
maxi = sz[there];
t = there;
}
}
if (maxi<=asz/2) return here;
else return cdfs(t,here,asz);
}
int findcen(int head) {
return cdfs(head,-1,idfs(head,-1));
}
void adfs(int here, int p, ll d, int step) {
int i;
dep[step][here] = d;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (there==p||dead[there]) continue;
adfs(there,here,d+lis[here][i].first,step);
}
}
int tt;
int cendc(int head, int step) {
int cen = findcen(head), i;
stp[cen] = step;
num[cen] = tt;
ord[tt++] = cen;
adfs(cen,-1,0,step);
dead[cen] = true;
st[cen].push_back(num[cen]);
for (i=0;i<lis[cen].size();i++) {
int there = lis[cen][i].second;
if (dead[there]) continue;
st[cen].push_back(num[cendc(there,step+1)]);
}
en[num[cen]] = tt;
return cen;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
int i;
for (i=0;i<n-1;i++) {
lis[A[i]].push_back(pli(D[i],B[i]));
lis[B[i]].push_back(pli(D[i],A[i]));
}
cendc(0,0);
}
int xl[500100], yl[500100];
int x[500100], y[500100];
ll dnc(int sx, int ex, int sy, int ey, int idx) {
if (sx>=ex||sy>=ey) return (1LL<<60);
int beg = num[idx]; int stt = stp[idx], i, j;
ll minix = (1LL<<60), miniy = (1LL<<60);
for (i=sx;i<ex;i++) minix = min(minix,dep[stt][x[i]]);
for (i=sx;i<ex;i++) xl[i] = *(--upper_bound(st[idx].begin(),st[idx].end(),num[x[i]]));
for (i=sy;i<ey;i++) miniy = min(miniy,dep[stt][y[i]]);
for (i=sy;i<ey;i++) yl[i] = *(--upper_bound(st[idx].begin(),st[idx].end(),num[y[i]]));
ll res = minix+miniy;
i=sx; j=sy;
if (x[i]==idx) i++;
if (y[j]==idx) j++;
int ti = i, tj = j;
for (;i<ex;i++) {
if (i==ex-1||xl[i+1]!=xl[i]) {
for (;j<ey&&yl[j]<xl[i];j++);
tj = j;
for (;j<ey&&yl[j]==xl[i];j++);
res = min(res,dnc(ti,i+1,tj,j,ord[xl[i]]));
ti = i+1; tj = j;
}
}
return res;
}
bool cmp(int a, int b) {return num[a]<num[b];}
ll Query(int S, int X[], int T, int Y[]) {
int i;
for (i=0;i<S;i++) x[i] = X[i];
for (i=0;i<T;i++) y[i] = Y[i];
sort(x,x+S,cmp);
sort(y,y+T,cmp);
return dnc(0,S,0,T,ord[0]);
}
Compilation message
factories.cpp: In function 'int idfs(int, int)':
factories.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'int cdfs(int, int, int)':
factories.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'void adfs(int, int, ll, int)':
factories.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'int cendc(int, int)':
factories.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[cen].size();i++) {
^
factories.cpp: In function 'll dnc(int, int, int, int, int)':
factories.cpp:87:13: warning: unused variable 'beg' [-Wunused-variable]
int beg = num[idx]; int stt = stp[idx], i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
151760 KB |
Output is correct |
| 2 |
Correct |
633 ms |
152156 KB |
Output is correct |
| 3 |
Correct |
686 ms |
152156 KB |
Output is correct |
| 4 |
Correct |
576 ms |
152156 KB |
Output is correct |
| 5 |
Correct |
703 ms |
152236 KB |
Output is correct |
| 6 |
Correct |
643 ms |
152312 KB |
Output is correct |
| 7 |
Correct |
713 ms |
152156 KB |
Output is correct |
| 8 |
Correct |
669 ms |
152156 KB |
Output is correct |
| 9 |
Correct |
799 ms |
152236 KB |
Output is correct |
| 10 |
Correct |
676 ms |
152312 KB |
Output is correct |
| 11 |
Correct |
753 ms |
152156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
151760 KB |
Output is correct |
| 2 |
Correct |
2739 ms |
193736 KB |
Output is correct |
| 3 |
Correct |
4149 ms |
195684 KB |
Output is correct |
| 4 |
Correct |
1373 ms |
193256 KB |
Output is correct |
| 5 |
Correct |
5196 ms |
212168 KB |
Output is correct |
| 6 |
Correct |
3856 ms |
195356 KB |
Output is correct |
| 7 |
Correct |
1289 ms |
160456 KB |
Output is correct |
| 8 |
Correct |
1059 ms |
160620 KB |
Output is correct |
| 9 |
Correct |
1119 ms |
162812 KB |
Output is correct |
| 10 |
Correct |
1022 ms |
160380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3613 ms |
193736 KB |
Output is correct |
| 2 |
Correct |
3313 ms |
193736 KB |
Output is correct |
| 3 |
Correct |
5479 ms |
194940 KB |
Output is correct |
| 4 |
Correct |
5273 ms |
195376 KB |
Output is correct |
| 5 |
Correct |
5443 ms |
195272 KB |
Output is correct |
| 6 |
Execution timed out |
6000 ms |
207828 KB |
Execution timed out |
| 7 |
Halted |
0 ms |
0 KB |
- |
