oj.uz

Submission #66371

# Submission time Handle Problem Language Result Execution time Memory
66371 2018-08-10T10:37:23 Z mirbek01 Shortcut (IOI16_shortcut) C++17
0 / 100
 3 ms 560 KB 
# include "shortcut.h"
# include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 2;

int vr, n;
long long sum, d[N];
vector < pair <int, int> > g[N];
vector <int> vec;

void dfs(int v){
      for(int i = 0; i < n; i ++)
            d[i] = 1e18;
      d[v] = 0;
      set < pair <long long, int> > st;
      st.insert({0, v});
      while(!st.empty()){
            int vv = st.begin()->second;
            st.erase(st.begin());
            for(auto to : g[vv]){
                  if(d[vv] + to.second < d[to.first]){
                        st.erase({to.first, d[to.first]});
                        d[to.first] = d[vv] + to.second;
                        st.insert({d[to.first], to.first});
                  }
            }
      }
      sum = 0;
      for(int i = 0; i < n; i ++){
            long long cur = vec[v] + d[i];
            if(i != v) cur += vec[i];
            if(sum < cur){
                  sum = cur;
                  vr = i;
            }
      }
}

long long find_shortcut(int NN, vector<int> l, vector<int> d, int c){
      n = NN;
      long long ans = 1e18;
      for(int i = 0; i < n - 1; i ++){
            g[i].push_back({i + 1, l[i]});
            g[i + 1].push_back({i, l[i]});
      }
      vec = d;
      for(int i = 1; i < n; i ++){
            for(int j = 2 + 1; j < n; j ++){
                  g[i].push_back({j, c});
                  g[j].push_back({i, c});
                  dfs(0);
                  dfs(vr);
                  ans = min(ans, sum);
                  g[i].pop_back();
                  g[j].pop_back();
            }
      }
      return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 376 KB n = 9, 110 is a correct answer
3 Incorrect 3 ms 560 KB n = 4, incorrect answer: jury 21 vs contestant 22
4 Halted 0 ms 0 KB -