#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=5e5+5;
vector<pii>adj[mxn];
int cnt[mxn];
bool vis[mxn];
vector<pair<int,long long>>p[mxn];
pair<long long,long long> mn[mxn];
void cnt_sz(int v,int pa){
cnt[v]=1;
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
cnt_sz(u,v);
cnt[v]+=cnt[u];
}
}
int find_cen(int v,int pa,int tar){
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
if(cnt[u]*2>tar)return find_cen(u,v,tar);
}
return v;
}
void dfs(int v,int pa,int top,int cur){
p[v].pb({top,cur});
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
dfs(u,v,top,cur+d);
}
}
void cen(int v){
cnt_sz(v,v);
v=find_cen(v,v,cnt[v]);
vis[v]=1;
dfs(v,v,v,0);
for(auto [u,d]:adj[v]){
if(vis[u])continue;
cen(u);
}
}
void Init(int N,int A[],int B[],int D[]){
for(int i=0;i<N-1;i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
cen(1);
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
mn[u]={1e18,1e18};
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
mn[u]={1e18,1e18};
}
}
long long ans=1e18;
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
chmin(mn[u].F,l);
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
chmin(mn[u].S,l);
chmin(ans,mn[u].F+mn[u].S);
}
}
for(int i=0;i<S;i++){
for(auto [u,l]:p[X[i]]){
chmin(ans,mn[u].F+mn[u].S);
}
}
for(int i=0;i<T;i++){
for(auto [u,l]:p[Y[i]]){
chmin(ans,mn[u].F+mn[u].S);
}
}
return ans;
}
/*
input:
*/
Compilation message
factories.cpp: In function 'void cnt_sz(int, int)':
factories.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'int find_cen(int, int, int)':
factories.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'void cen(int)':
factories.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for(auto [u,d]:adj[v]){
| ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:80:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
80 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto [u,l]:p[Y[i]]){
| ^
factories.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:96:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for(auto [u,l]:p[Y[i]]){
| ^
factories.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | for(auto [u,l]:p[X[i]]){
| ^
factories.cpp:107:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | for(auto [u,l]:p[Y[i]]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
45660 KB |
Output is correct |
| 2 |
Correct |
277 ms |
50700 KB |
Output is correct |
| 3 |
Incorrect |
299 ms |
51152 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
45656 KB |
Output is correct |
| 2 |
Correct |
1780 ms |
203460 KB |
Output is correct |
| 3 |
Incorrect |
2665 ms |
273848 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
45660 KB |
Output is correct |
| 2 |
Correct |
277 ms |
50700 KB |
Output is correct |
| 3 |
Incorrect |
299 ms |
51152 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
