Submission #525185

#	Time	Username	Problem	Language	Result	Execution time	Memory
525185		Dilshod_Imomov	Evacuation plan (IZhO18_plan)	C++17	100 / 100	713 ms	42436 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];
int d[N], used[N], sz[N], pr[N], ans[N];
set < int > qr[N];

int find_set( int a ) {
   if ( pr[a] == a ) {
      return a;
   }
   return pr[a] = find_set(pr[a]);
}

void merge( int a, int b, int val ) {
   a = find_set(a);
   b = find_set(b);
   if ( a == b ) {
      return;
   }
   if ( sz[a] < sz[b] ) {
      swap( a, b );
   }
   // cout << a << ' ' << b << ' ' << val << endl;
   for ( auto i: qr[b] ) {
      if ( qr[a].find(i) != qr[a].end() ) {
         // cout << i << endl;
         ans[i] = val;
         qr[a].erase(i);
      }
      else {
         qr[a].insert(i);
      }
   }
   qr[b].clear();
   sz[a] += sz[b];
   pr[b] = a;
}

int32_t main() {
   speed;
   int n, m;
   cin >> n >> m;
   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;
      pr[i] = i;
      sz[i] = 1;
   } 
   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 } );
         }
      }
   }
   int q;
   cin >> q;
   for ( int i = 1; i <= q; i++ ) {
      int u, v;
      cin >> u >> v;
      qr[u].insert(i);
      qr[v].insert(i);
   }
   vector < pair < int, int > > vc;
   for ( int i = 1; i <= n; i++ ) {
      vc.push_back( { d[i], i } );
   }
   sort( vc.rbegin(), vc.rend() );
   for ( int i = 0; i < n; i++ ) {
      int v = vc[i].se;
      used[v] = 1;
      // cout << "-> " << v << ' ' << d[v] << endl;
      for ( auto pr: adj[v] ) {
         int u = pr.fi;
         if ( used[u] ) {
            // cout << v << ' ' << u << endl;
            merge(v, u, d[v]);
         }
      }
   }
   for ( int i = 1; i <= q; i++ ) {
      cout << ans[i] << "\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: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46