#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
vii ke[maxn];
int par[maxn][20],sz[maxn];
long long d[maxn];
int ind[maxn],head[maxn],cnt = 1;
long long minn[maxn][20];
vector<array<long long,4>> adj;
void dfs(int u,int parent)
{
sz[u] = 1;
for(auto [v,w] : ke[u])
{
if(v == parent) continue;
par[v][0] = u;
d[v] = d[u] + w;
dfs(v,u);
sz[u] += sz[v];
}
}
void hld(int u,int parent)
{
if(head[cnt] == 0) head[cnt] = u;
ind[u] = cnt;
int sc = -1,maxx = -1;
for(auto [v,w] : ke[u]) if(v != parent)
{
if(maxx < sz[v])
{
maxx = sz[v];
sc = v;
}
}
if(sc != -1) hld(sc,u);
for(auto [v,w] : ke[u]) if(v != parent and v != sc)
{
cnt++;
hld(v,u);
}
}
void get(int u,int t)
{
long long val = d[u];
int uchain,vchain = ind[1];
while(1)
{
uchain = ind[u];
adj.push_back({(long long)uchain,(long long)u,val,(long long)t});
if(uchain == vchain) return;
u = ind[u];
u = par[head[u]][0];
}
}
void Init(int N,int A[],int B[],int D[])
{
fo(i,0,N - 2)
{
ke[A[i] + 1].pb(B[i] + 1,D[i]);
ke[B[i] + 1].pb(A[i] + 1,D[i]);
}
dfs(1,1);
hld(1,1);
}
long long Query(int S, int X[], int T, int Y[])
{
long long ans = 2e18;
fo(i,0,S - 1) get(X[i] + 1,0);
fo(i,0,T - 1) get(Y[i] + 1,1);
sort(adj.begin(),adj.end(),[](array<long long,4> a,array<long long,4> b)
{
return d[a[1]] > d[b[1]];
});
fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
for(auto [p,v,dist,t] : adj)
{
ans = min(ans,minn[p][1 - t] - 2 * d[v] + dist);
minn[p][t] = min(minn[p][t],dist);
}
adj.clear();
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
49756 KB |
Output is correct |
2 |
Correct |
661 ms |
56940 KB |
Output is correct |
3 |
Correct |
488 ms |
65732 KB |
Output is correct |
4 |
Correct |
521 ms |
66516 KB |
Output is correct |
5 |
Correct |
302 ms |
63968 KB |
Output is correct |
6 |
Correct |
390 ms |
66016 KB |
Output is correct |
7 |
Correct |
496 ms |
65844 KB |
Output is correct |
8 |
Correct |
481 ms |
66144 KB |
Output is correct |
9 |
Correct |
301 ms |
64012 KB |
Output is correct |
10 |
Correct |
384 ms |
66052 KB |
Output is correct |
11 |
Correct |
465 ms |
65872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
49752 KB |
Output is correct |
2 |
Execution timed out |
8064 ms |
160244 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
49756 KB |
Output is correct |
2 |
Correct |
661 ms |
56940 KB |
Output is correct |
3 |
Correct |
488 ms |
65732 KB |
Output is correct |
4 |
Correct |
521 ms |
66516 KB |
Output is correct |
5 |
Correct |
302 ms |
63968 KB |
Output is correct |
6 |
Correct |
390 ms |
66016 KB |
Output is correct |
7 |
Correct |
496 ms |
65844 KB |
Output is correct |
8 |
Correct |
481 ms |
66144 KB |
Output is correct |
9 |
Correct |
301 ms |
64012 KB |
Output is correct |
10 |
Correct |
384 ms |
66052 KB |
Output is correct |
11 |
Correct |
465 ms |
65872 KB |
Output is correct |
12 |
Correct |
10 ms |
49752 KB |
Output is correct |
13 |
Execution timed out |
8064 ms |
160244 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |