Submission #525099

#	Time	Username	Problem	Language	Result	Execution time	Memory
525099		Dilshod_Imomov	Evacuation plan (IZhO18_plan)	C++17	10 / 100	4080 ms	55280 KiB

plan

# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # define int long long
# define fi first
# define se second

using namespace std;

const int N = 1e5 + 7;
const int mod = 1e9 + 7;
// const int INF = 1e18;

vector < pair < int, int > > adj[N];
vector < int > adj1[N];
int d[N], timer = 1, tin[N], tout[N], up[N][35], L, used[N], used1[N], t[4 * N], invtin[N];

void dfs( int v, int prv ) {
   up[v][0] = prv;
   used1[v] = 1;
   invtin[timer] = v;
   tin[v] = timer++;
   for ( int i = 1; i <= L; i++ ) {
      up[v][i] = up[up[v][i - 1]][i - 1];
   }
   // cout << v << ' ' << d[v] << endl;
   for ( auto u: adj1[v] ) {
      if ( u != prv ) {
         dfs(u, v);
      }
   }
   tout[v] = timer;
}


set < pair < int, int > > ST;

void rec( int v ) {
   used[v] = 1;
   for ( auto pr: adj[v] ) {
      int u = pr.fi;
      if ( !used[u] ) {
         ST.insert( {-d[u], u} );
      }
   }
   if ( !ST.empty() ) {
      int x = ST.begin()->se;
      adj1[v].push_back(x);
      adj1[x].push_back(v);
      ST.erase(ST.begin());
      rec( x );
   }
}

bool is_ancestor( int u, int v ) {
   return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca( int u, int v ) {
   if ( is_ancestor(u, v) ) {
      return u;
   }
   if ( is_ancestor(v, u) ) {
      return v;
   }
   for ( int i = L; i >= 0; i-- ) {
      if ( is_ancestor( up[v][i], u ) ) {
         v = up[v][i];
      }
   }
   return up[v][0];
}

void build( int v, int l, int r ) {
   if ( l == r ) {
      t[v] = d[ invtin[l] ];
   }
   else {
      int m = (l + r) / 2;
      build( v * 2, l, m );
      build( v * 2 + 1, m + 1, r );
      t[v] = min( t[v * 2], t[v * 2 + 1] );
   }
}

// int get( int v, int l, int  )

int32_t main() {
   speed;
   int n, m;
   cin >> n >> m;
   L = log2(n) + 1;
   for ( int i = 1; i <= m; i++ ) {
      int u, v, w;
      cin >> u >> v >> w;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
   }
   int k;
   cin >> k;
   set < pair < int, int > > st;
   for ( int i = 1; i <= n; i++ ) {
      d[i] = mod;
   } 
   for ( int i = 1; i <= k; i++ ) {
      int x;
      cin >> x;
      d[x] = 0;
      st.insert({0, x});
   }
   while ( !st.empty() ) {
      int v = st.begin()->se;
      st.erase( { d[v], v } );
      // cout << v << " " << d[v] << endl;
      for ( auto pr: adj[v] ) {
         int u = pr.fi, w = pr.se;
         if ( d[v] + w < d[u] ) {
            st.erase( { d[u], u } );
            d[u] = d[v] + w;
            st.insert( { d[u], u } );
         }
      }
   }
   rec( 1 );
   dfs(1, 1);
   build( 1, 1, n );
   int q;
   cin >> q;
   for ( int i = 1; i <= q; i++ ) {
      int a, b;
      cin >> a >> b;
      int lc = lca(a, b), mn = d[lc];
      while ( a != lc ) {
         mn = min( mn, d[a] );
         a = up[a][0];
      }
      while ( b != lc ) {
         mn = min( mn, d[b] );
         b = up[b][0];
      }
      cout << mn << '\n';
   }
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46