#include"factories.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
// ==========================(debug)============================================================================================== //
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
// ==========================(debug)============================================================================================== //
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;
// ==========================(MOD)=============================================================================================== //
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
// ==========================(MOD)=============================================================================================== //
bool f = false;
vector<pi> adj[mx];
ll st[mx];
ll en[mx];
ll tr[2*mx];
ll dep[mx];
ll timer;
ll dp[mx];
ll stt[2*mx][20];
ll loog[2*mx];
ll range;
vector<pi> lis[mx];
ll sz[mx];
bool mark[mx];
ll pd[mx];
void dfs(ll u,ll par){
st[u] = timer;
tr[timer] = u;
timer++;
fx(adj[u])
if(x.ff!=par){
dep[x.ff] = dep[u] + 1;
dp[x.ff] = dp[u] + x.ss;
dfs(x.ff,u);
}
en[u] = timer;
tr[timer] = u;
timer++;
return;
}
ll query(ll u,ll v){
range = loog[v-u+1];
return (dep[stt[u][range]] < dep[stt[v-(1<<range)+1][range]] ? dep[stt[u][range]] : dep[stt[v-(1<<range)+1][range]]);
}
ll lca(ll u,ll v){
if(st[u]<st[v] && en[u]>en[v])
return u;
if(st[u]>st[v] && en[u]<en[v])
return v;
if(st[u]>st[v])
swap(u,v);
return query(en[u],st[v]);
}
void dfs2(ll u,ll par){
sz[u] = 1;
fx(adj[u])
if(x.ff!=par && !mark[x.ff]){
dfs2(x.ff,u);
sz[u] += sz[x.ff];
}
return;
}
ll find(ll u,ll par,ll p){
fx(adj[u])
if(x.ff!=par && !mark[x.ff]){
if(sz[x.ff]*2>sz[p])
return find(x.ff,u,p);
}
return u;
}
ll dis(ll u,ll v){
return dp[u] + dp[v] - 2*dp[lca(u,v)];
}
void dfs3(ll u,ll par,ll d,ll p){
lis[u].push_back({p,d});
fx(adj[u])
if(x.ff!=par && !mark[x.ff]){
dfs3(x.ff,u,d+x.ss,p);
}
return;
}
void divide(ll u){
dfs2(u,-1);
u = find(u,-1,u);
// debug(u);
mark[u] = 1;
lis[u].push_back({u,0});
fx(adj[u])
if(!mark[x.ff])
dfs3(x.ff,u,x.ss,u);
fx(adj[u])
if(!mark[x.ff])
divide(x.ff);
}
void Init(int N, int A[], int B[], int D[]){
n = N;
fip(0,n-1){
A[i]++;
B[i]++;
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
loog[0] = loog[1] = 0;
fip(2,2*mx)
loog[i] = loog[i>>1] + 1;
dep[1] = 0;
dp[1] = 0;
timer = 0;
dfs(1,-1);
fip(0,timer)
stt[i][0ll] = tr[i];
fjp(1,20)
for(ll i = 0 ; i + (1<<j) - 1 < timer;i++)
stt[i][j] = (dep[stt[i][j-1]] < dep[stt[i+(1<<(j-1))][j-1]] ? dep[stt[i][j-1]] : dep[stt[i+(1<<(j-1))][j-1]]);
divide(1);
// fip(1,n+1){
// debug(lis[i]);
// }
fip(1,n+1)
pd[i] = 1e18;
return;
}
void update(ll u){
// debug(lis[u]);
fx(lis[u])
pd[x.ff] = min(pd[x.ff],x.ss);
return;
}
void query(ll u){
fx(lis[u])
ans = min(ans,dis(u,x.ff)+pd[x.ff]);
return;
}
void rollback(ll u){
fx(lis[u])
pd[x.ff] = 1e18;
return;
}
long long Query(int S, int X[], int T, int Y[]) {
fip(0,S){
X[i]++;
update(X[i]);
}
ans = 1e18;
fip(0,T){
Y[i]++;
query(Y[i]);
}
fip(0,S)
rollback(X[i]);
return ans;
}
/*int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input1.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
freopen("error1.txt", "w", stderr);
#endif // ONLINE_JUDGE
int N,M;
cin>>N>>M;
int A[N-1],B[N-1],D[N-1];
fip(0,N-1)
cin>>A[i]>>B[i]>>D[i];
Init(N,A,B,D);
fip(0,M){
int S,T;
cin>>S;
cin>>T;
int X[S];
fip(0,S)
cin>>X[i];
int Y[T];
fip(0,T)
cin>>Y[i];
cout<<Query(S,X,T,Y)<<nli;
}
cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
64092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
64092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
64092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
