Submission #48205

#	Time	Username	Problem	Language	Result	Execution time	Memory
48205		Lkvatashidze	Evacuation plan (IZhO18_plan)	C++17	0 / 100	880 ms	60060 KiB

plan

#include<bits/stdc++.h>
#define ll long long
const ll MAXN=100000;
const ll INF=10000000000;
using namespace std;

         vector < vector < ll > > dp(MAXN+5), dp_mn(MAXN+5);
         vector < vector < pair < ll, ll > > >  g(MAXN+5), tree(MAXN+5);
         ll time_in[MAXN+5], time_out[MAXN+5], parent[MAXN+5], pat[MAXN+5];
         ll n, m, timer, lg, rad, a, b;
         vector < ll > dist;
         set < pair < ll, pair < ll, ll > > > stk;
         set < pair < ll, pair < ll, ll > > > ::iterator stk_it;

      void make_set (ll);
      ll find_set(ll);
      void union_sets(ll,ll);
      void DFS (ll,ll,ll);
      ll get_min(ll,ll);
      ll lca (ll,ll);
      void sol();

      bool issubtree (ll a, ll b) {
        if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
            return true;

            return false;
 }

     int main () {

       ios_base::sync_with_stdio(false);

             cin >> n >> m;

         for (ll k=1; k<=m; k++) {
              ll x, y, z;
              cin >> x >> y >> z;
              g[x].push_back({y,z});
              g[y].push_back({x,z});
     }

         dist.resize(n+1,INF);
         set < pair < ll, ll > > st;

           cin >> rad;
        for (ll k=1; k<=rad; k++) {
             ll x;
             cin >> x;
             dist[x]=0;
             st.insert({dist[x],x});
        }

        while (!st.empty()) {
            ll v=(*st.begin()).second;
            st.erase(st.begin());
          for (ll k=0; k<g[v].size(); k++) {
            ll to=g[v][k].first; ll price=g[v][k].second;
            if (dist[to]>dist[v]+price) {
                st.erase({dist[to],to});
                dist[to]=dist[v]+price;
                st.insert({dist[to],to});
            }
          }
        }


        for (ll k=1; k<=n; k++)
             make_set(k);

       for (ll k=1; k<=n; k++)
        for (ll i=0; i<g[k].size(); i++) {
           ll x=k; ll y=g[k][i].first;
           g[k][i].second=min(dist[x],dist[y]);
           stk.insert({-g[k][i].second,{x,y}});
       }

          while (!stk.empty()) {
            stk_it=stk.begin();

            a=stk_it->second.first;
            b=stk_it->second.second;

            while (find_set(a)==find_set(b)) {
                    stk.erase(stk_it);
                    if (stk.empty()) break;
                    stk_it=stk.begin();
                    a=stk_it->second.first;
                    b=stk_it->second.second;
          }
            if (stk.empty()) break;

            union_sets(a,b);
            int price=stk_it->first;
            tree[a].push_back(make_pair(b,-price));
            tree[b].push_back(make_pair(a,-price));
            stk.erase(stk_it);
     }

            ll lg=log2(n+1);
        for (ll k=0; k<=n; k++) {
        dp[k].resize(lg+1);
        dp_mn[k].resize(lg+1);
     }

       DFS(1ll,0ll,INF);

     int Q;
       cin >> Q;

         while (Q--)
           sol();

     return 0;
}

   void sol() {
      int a, b;
      cin >> a >> b;
      int LCA=lca(a,b);

      ll answer=min(get_min(a,LCA),get_min(b,LCA));

      cout << answer << endl;
   }

   void make_set (ll v) {
      parent[v]=v;
   }

   ll find_set (ll v) {

     if (v==parent[v])
        return parent[v];

     return parent[v]=find_set(parent[v]);
 }

  void union_sets (ll a, ll b) {
       a=find_set(a);
       b=find_set(b);

             if (a!=b)
            parent[b]=a;
 }



 void DFS (ll v, ll p, ll d) {

    pat[v]=p;

    dp[v][0]=p;
    dp_mn[v][0]=d;


    for (ll k=1; k<=lg; k++) {
      dp[v][k]=dp[dp[v][k-1]][k-1];
       if (dp[v][k]!=0)
      dp_mn[v][k]=min(dp_mn[v][k-1],dp_mn[dp[v][k-1]][k-1]);
    }

    time_in[v]=timer++;

    for (ll k=0; k<tree[v].size(); k++) {
        ll to=tree[v][k].first;
        if (to==p) continue;
        DFS(to,v,tree[v][k].second);
    }

    time_out[v]=timer++;
}

  ll lca (ll a, ll b) {
    if (issubtree(a,b))
     return a;
    if (issubtree(b,a))
     return b;

    for (ll k=lg; k>=0; k--) {
      if (dp[a][k]==0) continue;
      if (issubtree(dp[a][k],b)) continue;
      a=dp[a][k];
    }

     return pat[a];
 }

 ll get_min (ll a, ll LCA) {

    ll counter=INF;

    for (ll k=lg; k>=0; k--) {
        if (dp[a][k]==0) continue;
        if (issubtree(dp[a][k],LCA) && dp[a][k]!=LCA) continue;
        counter=min(counter,dp_mn[a][k]);
        a=dp[a][k];
    }

     return counter;
 }

/*
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
*/

Compilation message (stderr)

plan.cpp: In function 'bool issubtree(long long int, long long int)':
plan.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if (time_in[a]<=time_in[b] && time_out[b]<=time_out[a])
         ^~
plan.cpp:27:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
             return false;
             ^~~~~~
plan.cpp: In function 'int main()':
plan.cpp:57:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for (ll k=0; k<g[v].size(); k++) {
                        ~^~~~~~~~~~~~
plan.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll i=0; i<g[k].size(); i++) {
                      ~^~~~~~~~~~~~
plan.cpp: In function 'void DFS(long long int, long long int, long long int)':
plan.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll k=0; k<tree[v].size(); k++) {
                  ~^~~~~~~~~~~~~~~

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