| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 371932 | RohamIzadidoost | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
#include "factories.h"
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 = 19 ;
ll dis[maxn] , d[maxn] , ans , mark[maxn]; int L , R , h[maxn] , par[lg][maxn] , n , st[maxn] , ft[maxn] , cnt , q[maxn];
vec<pll> adj[maxn] , g[maxn];
vec<int> t ;
queue<int> q ;
stack<int> s ;
bool cmp(const int &i ,const 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 ;
}