oj.uz

Submission #89697

# Submission time Handle Problem Language Result Execution time Memory
89697 2018-12-18T06:42:10 Z mirbek01 Evacuation plan (IZhO18_plan) C++17
0 / 100
 268 ms 16204 KB 
# 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];
                  }
            }
            ans = min(ans, mx[0][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];
                  }
            }
            ans = min(ans, mx[0][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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -