Submission #48196

#	Time	Username	Problem	Language	Result	Execution time	Memory
48196		Lkvatashidze	Evacuation plan (IZhO18_plan)	C++17	0 / 100	842 ms	53600 KiB

plan

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

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

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

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

            return false;
 }

     int main () {


          scanf ("%d%d", &n, &m);

         for (int k=1; k<=m; k++) {
              int x, y, z;
              scanf ("%d%d%d", &x, &y, &z);
              g[x].push_back({y,z});
              g[y].push_back({x,z});
     }

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

          scanf ("%d", &rad);
        for (int k=1; k<=rad; k++) {
             int x;
             scanf ("%d", &x);
             dist[x]=0;
             st.insert({dist[x],x});
        }

        while (!st.empty()) {
            int v=(*st.begin()).second;
            st.erase(st.begin());
          for (int k=0; k<g[v].size(); k++) {
            int to=g[v][k].first; int 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 (int k=1; k<=n; k++)
             make_set(k);

       for (int k=1; k<=n; k++)
        for (int i=0; i<g[k].size(); i++) {
           int x=k; int 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);
     }

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

       DFS(1,0,INF);

     int Q;
       scanf ("%d", &Q);

         while (Q--)
           sol();

     return 0;
}

   void sol() {
      int a, b;
      scanf ("%d%d", &a, &b);
      int LCA=lca(a,b);

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

      printf ("%d\n", answer);
   }

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

   int find_set (int v) {

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

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

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

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



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

    pat[v]=p;

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


    for (int 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 (int k=0; k<tree[v].size(); k++) {
        int to=tree[v][k].first;
        if (to==p) continue;
        DFS(to,v,tree[v][k].second);
    }

    time_out[v]=timer++;
}

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

    for (int 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];
 }

 int get_min (int a, int LCA) {

    ll counter=INF;

    for (int 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(int, 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:56:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for (int k=0; k<g[v].size(); k++) {
                         ~^~~~~~~~~~~~
plan.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<g[k].size(); i++) {
                       ~^~~~~~~~~~~~
plan.cpp:105:19: warning: overflow in implicit constant conversion [-Woverflow]
        DFS(1,0,INF);
                   ^
plan.cpp: In function 'void DFS(int, int, int)':
plan.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k=0; k<tree[v].size(); k++) {
                   ~^~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
           scanf ("%d%d", &n, &m);
           ~~~~~~^~~~~~~~~~~~~~~~
plan.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
               scanf ("%d%d%d", &x, &y, &z);
               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
           scanf ("%d", &rad);
           ~~~~~~^~~~~~~~~~~~
plan.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
              scanf ("%d", &x);
              ~~~~~~^~~~~~~~~~
plan.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf ("%d", &Q);
        ~~~~~~^~~~~~~~~~
plan.cpp: In function 'void sol()':
plan.cpp:118:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%d%d", &a, &b);
       ~~~~~~^~~~~~~~~~~~~~~~

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