#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 5000*100+5 ;
const ll inf = 9223372036775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int h[maxn] , st[maxn] , cnt , ft[maxn] , par[lg][maxn] , n , Q , mark[maxn] ; ll ans , d[maxn] , dis[maxn] ;
vec<pii> adj[maxn] , g[maxn];
vec<int> t ;
queue<int> q ;
stack<int> s ;
bool cmp(int i , int j){
return (st[i] < st[j]) ;
}
void predfs(int v , int p){
st[v] = cnt ; cnt++ ;
for(auto u : adj[v]){
if(u.X != p){
h[u.X] = h[v] + 1 ;
dis[u.X] = dis[v] + u.Y ;
par[0][u.X] = v ;
for(int i = 1 ;i <lg ; i ++ ) par[i][u.X] = par[i-1][par[i-1][u.X]] ;
predfs(u.X , v) ;
}
}
ft[v] = cnt ;
}
int lca(int u , int v){
if(h[u] > h[v]) swap(u , v) ;
for(int i = lg- 1 ; i >= 0 ; i -- ){
if(par[i][v] != -1 && h[par[i][v]] >= h[u]) v = par[i][v] ;
}
if(v==u) return v ;
for(int i = lg - 1 ; i>= 0 ; i -- ){
if(par[i][v] != par[i][u]){
v = par[i][v] ;
u = par[i][u] ;
}
}
return par[0][u] ;
}
/*int main(){
cin>>n>>Q ;
for(int i = 1 ; i < n ; i ++ ){
ll u , v , w ;
cin>>u>>v>>w ;
adj[u].pb({v , w}) ;
adj[v].pb({u , w}) ;
}
for(int i = 0 ;i < lg ; i ++ ) par[i][0] = -1 ;
predfs(0 , -1) ;
while(Q--){
int S , T ;
cin>>S>>T ;
int X[S] , Y[T] ;
for(int i = 0 ; i < S ; i ++ ) cin>>X[i] ;
for(int i = 0 ; i < T ; i ++ ) cin>>Y[i] ;
//////////////////////////////////////////
for(int i = 0 ; i < S ; i ++ ){
t.pb(X[i]) ;
q.push(X[i]) ;
}
for(int i = 0 ; i <T ; i ++ ){
t.pb(Y[i]) ; mark[Y[i]] = 1 ;
}
sort(all(t) , cmp) ;
for(int i = 0 ; i < T + S - 1 ; i ++ ){
t.pb(lca(t[i] , t[i + 1])) ;
}t.pb(lca(t[T+S-1] , t[0])) ;
sort(all(t) , cmp) ; t.resize(unique(all(t)) - t.begin()) ;
for(auto u : t){
d[u] = inf ;
while(s.size() && !( st[s.top()] < st[u] && ft[u] <= ft[s.top()] ) ) s.pop() ;
if(s.size()){
g[u].pb({s.top() , dis[u] - dis[s.top()] }) ;
g[s.top()].pb({u , dis[u] - dis[s.top()] }) ;
}
s.push(u) ;
}
for(int i = 0 ; i < S ; i ++ ) d[X[i]] = 0 ;
ans = inf ;
while(SZ(q)){
int v = q.front() ;
q.pop() ;
for(auto u : g[v]){
if(d[u.X] > d[v] + u.Y){
d[u.X] = d[v] + u.Y ;
q.push(u.X) ;
if(mark[u.X])ans = min(ans , d[u.X]) ;
}
}
}
for(auto u : t){
g[u].clear() ;
}
for(int i = 0 ; i < T ; i ++ ) mark[Y[i]] = 0 ;
while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
cout<<ans << endl ;
///////////////////
}
}*/
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]}) ;
}
for(int i = 0 ;i < lg ; i ++ ) par[i][0] = -1 ;
predfs(0 , -1) ;
}
long long Query(int S , int X[] , int T , int Y[]){
for(int i = 0 ; i < S ; i ++ ){
t.pb(X[i]) ;
q.push(X[i]) ;
}
for(int i = 0 ; i <T ; i ++ ){
t.pb(Y[i]) ; mark[Y[i]] = 1 ;
}
sort(all(t) , cmp) ;
for(int i = 0 ; i < T + S - 1 ; i ++ ){
t.pb(lca(t[i] , t[i + 1])) ;
}t.pb(lca(t[T+S-1] , t[0])) ;
sort(all(t) , cmp) ; t.resize(unique(all(t)) - t.begin()) ;
for(auto u : t){
d[u] = inf ;
while(s.size() && !( st[s.top()] < st[u] && ft[u] <= ft[s.top()] ) ) s.pop() ;
if(s.size()){
g[u].pb({s.top() , dis[u] - dis[s.top()] }) ;
g[s.top()].pb({u , dis[u] - dis[s.top()] }) ;
}
s.push(u) ;
}
for(int i = 0 ; i < S ; i ++ ) d[X[i]] = 0 ;
ans = inf ;
while(SZ(q)){
int v = q.front() ;
q.pop() ;
for(auto u : g[v]){
if(d[u.X] > d[v] + u.Y){
d[u.X] = d[v] + u.Y ;
q.push(u.X) ;
if(mark[u.X])ans = min(ans , d[u.X]) ;
}
}
}
for(auto u : t){
g[u].clear() ;
}
for(int i = 0 ; i < T ; i ++ ) mark[Y[i]] = 0 ;
while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
return ans ;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:166:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
166 | while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
| ^~~~~
factories.cpp:166:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
166 | while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
24428 KB |
Output is correct |
| 2 |
Correct |
1333 ms |
33392 KB |
Output is correct |
| 3 |
Correct |
1506 ms |
33272 KB |
Output is correct |
| 4 |
Execution timed out |
8060 ms |
33260 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
24172 KB |
Output is correct |
| 2 |
Correct |
3611 ms |
124140 KB |
Output is correct |
| 3 |
Execution timed out |
8048 ms |
105080 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
24428 KB |
Output is correct |
| 2 |
Correct |
1333 ms |
33392 KB |
Output is correct |
| 3 |
Correct |
1506 ms |
33272 KB |
Output is correct |
| 4 |
Execution timed out |
8060 ms |
33260 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
