Submission #89708

#	Time	Username	Problem	Language	Result	Execution time	Memory
89708		mirbek01	Evacuation plan (IZhO18_plan)	C++17	0 / 100	280 ms	16076 KiB

plan

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

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

void dfs(int v, int pr = 0){
      tin[v] = ++ timer;
      p[0][v] = pr;
      mx[0][v] = d[v];
      for(int i = 1; i < 20; i ++)
            p[i][v] = p[i - 1][ p[i - 1][v] ];
      for(int i = 1; i < 20; i ++)
            mx[i][v] = min(mx[i - 1][v], mx[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 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});
      }

      d[0] = 0;

      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;
                        if(d[to] >= d[root]){
                              root = to;
                        }
                        st.insert({d[to], to});
                  }
            }
      }

      for(int i = 1; i <= n; i ++){
            if(root == i)
                  continue;
            int id = g[i][0].first;
            for(int j = 1; j < g[i].size(); j ++){
                  int to = g[i][j].first;
                  if(d[id] < d[to])
                        id = to;
            }
            gr[i].push_back(id);
            gr[id].push_back(i);
      }

      dfs(root);

      scanf("%d", &q);

      while(q --){
            int a, b;
            scanf("%d %d", &a, &b);
            int lc = lca(a, b);
            long long ans = 2e18;
            for(int i = 19; i >= 0; i --){
                  if(p[i][a] && !upper(p[i][a], lc)){
                        ans = min(ans, mx[i][a]);
                        a = p[i][a];
                  }
            }
            if(lc != a)
                  ans = min(ans, mx[1][a]);
            for(int i = 19; i >= 0; i --){
                  if(p[i][b] && !upper(p[i][b], lc)){
                        ans = min(ans, mx[i][b]);
                        b = p[i][b];
                  }
            }
            if(lc != b)
                  ans = min(ans, mx[1][b]);
            cout << ans << 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:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < g[v].size(); i ++){
                            ~~^~~~~~~~~~~~~
plan.cpp:89:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 1; j < g[i].size(); j ++){
                            ~~^~~~~~~~~~~~~
plan.cpp:47: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:51: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:58:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &k);
       ~~~~~^~~~~~~~~~
plan.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
plan.cpp:100:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &q);
       ~~~~~^~~~~~~~~~
plan.cpp:104: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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46