Submission #89716

#	Time	Username	Problem	Language	Result	Execution time	Memory
89716		mirbek01	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1127 ms	36892 KiB

plan

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, q, k, p[20][N], tin[N], tout[N], timer, used[N], c[N];
long long d[N];
set < pair<long long, int> > st;
vector < pair <int, int> > g[N], vec;
vector <int> gr[N];

void dfs(int v, int pr = 0){
      tin[v] = ++ timer;
      p[0][v] = pr;
      for(int i = 1; i < 20; i ++)
            p[i][v] = p[i - 1][ p[i - 1][v] ];
      for(int to : gr[v]){
            if(to == pr)
                  continue;
            dfs(to, v);
      }
      tout[v] = timer;
}

bool upper(int a, int b){
      return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b){
      if(upper(a, b))
            return a;
      if(upper(b, a))
            return b;
      for(int i = 19; i >= 0; i --){
            if(p[i][a] && !upper(p[i][a], b)){
                  a = p[i][a];
            }
      }
      return p[0][a];
}

int get(int v){
      return c[v] == v?v:c[v] = get(c[v]);
}

void unite(int a, int b){
      a = get(a);
      b = get(b);
      if(a != b){
            c[b] = a;
      }
}

int main(){
      scanf("%d %d", &n, &m);

      for(int i = 1; i <= m; i ++){
            int s, e, w;
            scanf("%d %d %d", &s, &e, &w);
            g[s].push_back({e, w});
            g[e].push_back({s, w});
      }

      memset(d, 0x3f3f3f3f, sizeof(d));

      scanf("%d", &k);

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

      while(!st.empty()){
            int v = st.begin()->second;
            st.erase(st.begin());
            for(int i = 0; i < g[v].size(); i ++){
                  int to = g[v][i].first, len = g[v][i].second;
                  if(d[v] + len < d[to]){
                        st.erase({d[to], to});
                        d[to] = d[v] + len;
                        st.insert({d[to], to});
                  }
            }
      }

      for(int i = 1; i <= n; i ++){
            vec.push_back({d[i], i});
            c[i] = i;
      }

      sort(vec.begin(), vec.end());
      reverse(vec.begin(), vec.end());

      for(int i = 0; i < (int)vec.size(); i ++){
            int v = vec[i].second;
            used[v] = 1;
            for(int j = 0; j < g[v].size(); j ++){
                  int to = get(g[v][j].first);
                  if(used[to]){
                        if(get(v) != to){
                              gr[v].push_back(to);
                              gr[to].push_back(v);
                              unite(v, to);
                        }
                  }
            }
      }

      dfs(vec.back().second);

      scanf("%d", &q);

      while(q --){
            int a, b;
            scanf("%d %d", &a, &b);
            int lc = lca(a, b);
            cout << d[lc] << endl;
      }
}
/**
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
***/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < g[v].size(); i ++){
                            ~~^~~~~~~~~~~~~
plan.cpp:100:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < g[v].size(); j ++){
                            ~~^~~~~~~~~~~~~
plan.cpp:56:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
       ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &s, &e, &w);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &k);
       ~~~~~^~~~~~~~~~
plan.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
plan.cpp:114:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &q);
       ~~~~~^~~~~~~~~~
plan.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

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