#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 ;
ll h[maxn] , dis[maxn] , st[maxn] , cnt , ft[maxn] , par[lg][maxn] , n , d[maxn] , Q , ans , mark[maxn];
vec<pll> 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[])
{
migmig ;
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:2: warning: ignoring #pragma comment [-Wunknown-pragmas]
2 | #pragma comment(linker, "/stack:200000000")
|
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
from /usr/include/c++/9/ext/atomicity.h:35,
from /usr/include/c++/9/bits/ios_base.h:39,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from factories.cpp:4:
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
71 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
72 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
73 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
74 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
75 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
89 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
99 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:169:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
169 | while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
| ^~~~~
factories.cpp:169:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
169 | while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
| ^
