#include<bits/stdc++.h>
#include "factories.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define f first
#define s second
#define pii pair<ll,ll>
#define piii pair<ll,pair<ll,ll>>
#define vii vector<vector<ll>>
#define vi vector<ll>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const ll LIM=5000;
const string name="template";
ll n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
ll time_dfs=0;
pii euler_tour[1000005],sparse_table[20][LIM+5];
ll dist[LIM+5];
ll tin[LIM+5],tout[LIM+5],h[LIM+5],up_weight[20][LIM+5],low[20][LIM+5];
vector<ll> List;
priority_queue<pii,vector<pii>,greater<pii>> pq;
void dfs(ll u,ll parent,ll depth){
h[u] = depth;
tin[u] = time_dfs;
euler_tour[time_dfs++] = {depth,u};
low[0][u] = parent;
for(auto v:adj[u]){
if(v.f==parent) continue;
dfs(v.f,u,depth + 1);
euler_tour[time_dfs++] = {depth,u};
up_weight[0][v.f] = v.s;
}
tout[u] = time_dfs;
}
ll lca(ll u,ll v){
if(tin[u]>tin[v]){
swap(u,v);
}
ll bt = 63 - __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 lift_weight(ll u,ll k){
ll tmp=0;
ll w = 0;
while(k>0){
if(k%2==1){
w+=up_weight[tmp][u];
u=low[tmp][u];
}
k>>=1;
tmp++;
}
return w;
}
bool cmp(ll a,ll b){
return tin[a]<tin[b];
}
ll isSubtree(ll u,ll v)
{
return tin[u]<=tin[v] && tin[v]<=tout[u];
}
void Init(int N, int A[], int B[], int D[]){
n=N;
time_dfs=0;
for(ll i=0;i<n-1;++i){
A[i]++;
B[i]++;
}
for(ll 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(ll i=1;i<=n;++i){
dist[i]=-1;
}
dfs(1,0,0);
for(ll i=0;i<time_dfs;++i){
sparse_table[0][i] = euler_tour[i];
}
for(ll i=1;i<20;++i){
for(ll 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))]);
}
}
for(ll i=1;i<20;++i){
for(ll j=1;j<=n;++j){
low[i][j] =low[i-1][low[i-1][j]];
up_weight[i][j] = up_weight[i-1][j] + up_weight[i-1][low[i-1][j]];
}
}
}
long long Query(int S, int X[], int T, int Y[]){
List.clear();
for(ll i=0;i<S;++i){
List.push_back(++X[i]);
}
for(ll i=0;i<T;++i){
List.push_back(++Y[i]);
}
sort(List.begin(),List.end(),cmp);
for(ll i=1;i<S+T;++i){
List.push_back(lca(List[i],List[i-1]));
}
sort(List.begin(),List.end(),cmp);
List.erase(unique(List.begin(),List.end()),List.end());
vector<ll> st;
for(ll i=0;i<List.size();++i){
ll u = List[i];
while(st.size()>=2 && !isSubtree(st.back(),u)){
ll x = st[st.size()-2];
ll y= st.back();
ll LCA = lca(x,y);
ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
adj_vt[x].push_back({y,w});
adj_vt[y].push_back({x,w});
st.pop_back();
}
st.push_back(u);
}
while(st.size()>=2){
ll x = st[st.size()-2];
ll y= st.back();
ll LCA = lca(x,y);
ll w=lift_weight(x,h[x] - h[LCA]) + lift_weight(y,h[y] - h[LCA]);
adj_vt[x].push_back({y,w});
adj_vt[y].push_back({x,w});
st.pop_back();
}
for(ll i=0;i<T;++i){
pq.push({0,Y[i]});
}
while(!pq.empty()){
ll u = pq.top().s;
ll w= pq.top().f;
pq.pop();
if(dist[u]!=-1) continue;
dist[u] = w;
for(auto v:adj_vt[u]){
pq.push({w + v.s,v.f});
}
}
long long ans=LLONG_MAX;
for(ll i=0;i<S;++i){
ans = min(ans,dist[X[i]]);
}
for(auto x:List){
adj_vt[x].clear();
dist[x]=-1;
}
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:133:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(ll i=0;i<List.size();++i){
| ~^~~~~~~~~~~~
factories.cpp: In function 'long long int lca(long long int, long long int)':
factories.cpp:54:77: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
factories.cpp:21:25: note: while referencing 'sparse_table'
21 | pii euler_tour[1000005],sparse_table[20][LIM+5];
| ^~~~~~~~~~~~
factories.cpp:54:38: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~~~~~~~~~^
factories.cpp:21:25: note: while referencing 'sparse_table'
21 | pii euler_tour[1000005],sparse_table[20][LIM+5];
| ^~~~~~~~~~~~
factories.cpp:54:55: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~^
factories.cpp:54:30: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~^
factories.cpp:54:55: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~^
factories.cpp:54:30: warning: array subscript 31 is above array bounds of 'std::pair<long long int, long long int> [20][5005]' [-Warray-bounds]
54 | pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
| ~~~~~~~~~~~~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
1364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
