//#include "factories.h"
#include <bits/stdc++.h>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef std::pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define MAXN 500000
using namespace std;
vector<pii> a[MAXN];
//vector<int> b[MAXN];
bool done[MAXN];
int sz[MAXN], par[MAXN];
char lvl[MAXN];
ll d[MAXN][19];
ll ans[MAXN];
void dfs(int cur, int last){
sz[cur] = 1;
for(pii i : a[cur]){
if(i.f!= last && !done[i.f]){
dfs(i.f,cur); sz[cur]+=sz[i.f];
}
}
}
int Cen(int cur, int last, int tot){
for(pii i : a[cur]){
if(i.f == last || done[i.f]) continue;
if(sz[i.f]<<1 > tot){
return Cen(i.f, cur, tot);
}
}
return cur;
}
void minDis(int cur, int last, ll dis, char lvl){
d[cur][lvl] = dis;
for(pii i : a[cur]){
if(i.f==last||done[i.f]) continue;
minDis(i.f,cur,dis+i.s,lvl);
}
}
int decomp(int rt, char lv){
dfs(rt, -1);
int cen = Cen(rt, -1, sz[rt]);
done[cen] = 1;
lvl[cen] = lv;
minDis(cen,-1,0,lv);
for(pii i : a[cen]){
if(!done[i.f]){
int sub = decomp(i.f, lv + 1);
par[sub] = cen;
// b[cen].pb(sub);
// b[sub].pb(cen) ;
}
}
return cen;
}
/*
16 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 4 2 4 3 4 4 5 5 6 6 7 7 8 7 9 6 10 10 11 11 12 11 13 12 14 13 15 13 16
*/
void Init(int N, int A[], int B[], int D[]){
MEM(ans, INF);
for(int i = 0; i < N-1; i++){
a[A[i]].pb({B[i],D[i]});
a[B[i]].pb({A[i],D[i]});
}
par[decomp(1,0)] = -1;
}
long long Query(int S, int X[], int T, int Y[]){
for(int k = 0; k < S; k++){
int cur = X[k];
while(cur!=-1){
ans[cur] = min(ans[cur],d[X[k]][lvl[cur]]);
cur = par[cur];
}
}
ll ret = INF;
for(int k = 0; k < T; k++){
int cur = Y[k];
while(cur!=-1){
ret = min(ret, ans[cur] + d[Y[k]][lvl[cur]]);
//cout<<cur<<endl;
cur = par[cur];
}
}
for(int k = 0; k < S; k++){
int cur = X[k];
while(cur!=-1){
ans[cur] = INF;
cur = par[cur];
}
}
//cout<<endl;
return ret;
}
//
//int main(){
// cin.sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//// int n,q;
//// cin>>n>>q;
//// int a[n], b[n],d2[n];
//// for(int i = 0; i < n-1;i++){
//// cin>>a[i]>>b[i]>>d2[i];
//// }
//// Init(n,a,b,d2);
////// for(int i = 0; i < n; i++){
////// cout<<lvl[i]<<endl;
////// }
////// while(1){
////// int x,y;
////// cin>>x>>y;
////// cout<<d[x][y]<<endl;
////// }
////
//// int s,t;
//// for(int i = 0; i < q; i++){
//// cin>>s>>t;
//// int x[s], y[t];
//// for(int j = 0; j < s; j++){
//// cin>>x[j];
//// }
//// for(int j = 0; j < t; j++){
//// cin>>y[j];
//// }
//// cout<<Query(s,x,t,y)<<endl;
//// }
//
//
//}
Compilation message
factories.cpp: In function 'void minDis(int, int, ll, char)':
factories.cpp:40:15: warning: array subscript has type 'char' [-Wchar-subscripts]
d[cur][lvl] = dis;
^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:72:14: warning: overflow in implicit constant conversion [-Woverflow]
factories.cpp:4:29:
#define MEM(a, b) memset(a, (b), sizeof(a))
~~~
factories.cpp:72:14:
MEM(ans, INF);
factories.cpp:4:30: note: in definition of macro 'MEM'
#define MEM(a, b) memset(a, (b), sizeof(a))
^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:84:53: warning: array subscript has type 'char' [-Wchar-subscripts]
ans[cur] = min(ans[cur],d[X[k]][lvl[cur]]);
^
factories.cpp:93:55: warning: array subscript has type 'char' [-Wchar-subscripts]
ret = min(ret, ans[cur] + d[Y[k]][lvl[cur]]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
16376 KB |
Output is correct |
2 |
Correct |
373 ms |
25292 KB |
Output is correct |
3 |
Correct |
418 ms |
25384 KB |
Output is correct |
4 |
Correct |
393 ms |
25384 KB |
Output is correct |
5 |
Correct |
429 ms |
25520 KB |
Output is correct |
6 |
Correct |
294 ms |
25520 KB |
Output is correct |
7 |
Correct |
412 ms |
25520 KB |
Output is correct |
8 |
Correct |
404 ms |
25520 KB |
Output is correct |
9 |
Correct |
414 ms |
25520 KB |
Output is correct |
10 |
Correct |
311 ms |
25520 KB |
Output is correct |
11 |
Correct |
423 ms |
25520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
25520 KB |
Output is correct |
2 |
Correct |
2617 ms |
127136 KB |
Output is correct |
3 |
Correct |
4254 ms |
128076 KB |
Output is correct |
4 |
Correct |
1152 ms |
128076 KB |
Output is correct |
5 |
Correct |
5439 ms |
151668 KB |
Output is correct |
6 |
Correct |
4295 ms |
151668 KB |
Output is correct |
7 |
Correct |
1224 ms |
151668 KB |
Output is correct |
8 |
Correct |
552 ms |
151668 KB |
Output is correct |
9 |
Correct |
1412 ms |
151668 KB |
Output is correct |
10 |
Correct |
1259 ms |
151668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
16376 KB |
Output is correct |
2 |
Correct |
373 ms |
25292 KB |
Output is correct |
3 |
Correct |
418 ms |
25384 KB |
Output is correct |
4 |
Correct |
393 ms |
25384 KB |
Output is correct |
5 |
Correct |
429 ms |
25520 KB |
Output is correct |
6 |
Correct |
294 ms |
25520 KB |
Output is correct |
7 |
Correct |
412 ms |
25520 KB |
Output is correct |
8 |
Correct |
404 ms |
25520 KB |
Output is correct |
9 |
Correct |
414 ms |
25520 KB |
Output is correct |
10 |
Correct |
311 ms |
25520 KB |
Output is correct |
11 |
Correct |
423 ms |
25520 KB |
Output is correct |
12 |
Correct |
19 ms |
25520 KB |
Output is correct |
13 |
Correct |
2617 ms |
127136 KB |
Output is correct |
14 |
Correct |
4254 ms |
128076 KB |
Output is correct |
15 |
Correct |
1152 ms |
128076 KB |
Output is correct |
16 |
Correct |
5439 ms |
151668 KB |
Output is correct |
17 |
Correct |
4295 ms |
151668 KB |
Output is correct |
18 |
Correct |
1224 ms |
151668 KB |
Output is correct |
19 |
Correct |
552 ms |
151668 KB |
Output is correct |
20 |
Correct |
1412 ms |
151668 KB |
Output is correct |
21 |
Correct |
1259 ms |
151668 KB |
Output is correct |
22 |
Correct |
2987 ms |
151668 KB |
Output is correct |
23 |
Correct |
2862 ms |
151668 KB |
Output is correct |
24 |
Correct |
4183 ms |
151668 KB |
Output is correct |
25 |
Correct |
3804 ms |
151668 KB |
Output is correct |
26 |
Correct |
3749 ms |
151668 KB |
Output is correct |
27 |
Correct |
4820 ms |
158620 KB |
Output is correct |
28 |
Correct |
1375 ms |
158620 KB |
Output is correct |
29 |
Correct |
4687 ms |
158620 KB |
Output is correct |
30 |
Correct |
4607 ms |
158620 KB |
Output is correct |
31 |
Correct |
4567 ms |
158620 KB |
Output is correct |
32 |
Correct |
1483 ms |
158620 KB |
Output is correct |
33 |
Correct |
547 ms |
158620 KB |
Output is correct |
34 |
Correct |
802 ms |
158620 KB |
Output is correct |
35 |
Correct |
821 ms |
158620 KB |
Output is correct |
36 |
Correct |
1159 ms |
158620 KB |
Output is correct |
37 |
Correct |
1141 ms |
158620 KB |
Output is correct |