oj.uz

Submission #297209

# Submission time Handle Problem Language Result Execution time Memory
297209 2020-09-11T11:20:40 Z Bruteforceman Olympic Bus (JOI20_ho_t4) C++11
16 / 100
 899 ms 5456 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5e4 + 10;
const long long inf = 1e15;
bool del[maxm];
int l[maxm], r[maxm], w[maxm], c[maxm];
int n, m;
vector <int> g[maxn];
bool imp[maxm];

vector <long long> shortest_path(int src, bool rev = false, bool mark = false) {
  vector <long long> d (n, inf);
  vector <bool> done (n, false);
  d[src] = 0;
  while(true) {
    int x = -1;
    for(int i = 0; i < n; i++) {
      if(done[i]) continue;
      if(x == -1 || d[x] > d[i]) {
        x = i;
      }
    }
    if(x == -1) break;
    done[x] = true;
    for(int e : g[x]) {
      if(del[e]) continue;
      if(rev && l[e] == x) continue;
      if(!rev && r[e] == x) continue;
      int y = l[e] ^ r[e] ^ x;
      if(d[y] > d[x] + w[e]) {
        d[y] = d[x] + w[e];
      }
    }
  }
  if(mark) {
    vector <int> par (n, -1);
    for(int x = 0; x < n; x++) {
      for(int e : g[x]) {
        if(del[e]) continue;
        if(rev && l[e] == x) continue;
        if(!rev && r[e] == x) continue;
        int y = l[e] ^ r[e] ^ x;
        if(d[y] == d[x] + w[e]) {
          par[y] = e;
        }
      }
    }
    for(int i = 0; i < n; i++) if(par[i] != -1) imp[par[i]] = true;
  }
  return d;
}
int main() {
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    cin >> l[i] >> r[i] >> w[i] >> c[i];
    l[i] -= 1;
    r[i] -= 1;
    g[l[i]].push_back(i);
    g[r[i]].push_back(i);
  }
  
  vector <long long> srcPath (m, inf), desPath(m, inf);
  vector <long long> leftSrc (m, inf), srcRight (m, inf);
  vector <long long> leftDes (m, inf), desRight (m, inf);
  
  fill(imp, imp + m, false);
  auto fromSrc = shortest_path(0, false, true);
  for(int i = 0; i < m; i++) {
    if(imp[i]) {
      del[i] = true;
      auto u = shortest_path(0); 
      srcPath[i] = u[n - 1];
      srcRight[i] = u[r[i]];
      del[i] = false;
    } else {
      srcPath[i] = fromSrc[n - 1];
      srcRight[i] = fromSrc[r[i]]; 
    }
  }

  fill(imp, imp + m, false);
  auto fromDes = shortest_path(n - 1, false, true);
  for(int i = 0; i < m; i++) {
    if(imp[i]) {
      del[i] = true;
      auto v = shortest_path(n - 1);
      desRight[i] = v[r[i]];
      desPath[i] = v[0]; 
      del[i] = false;
    } else {
      desRight[i] = fromDes[r[i]];
      desPath[i] = fromDes[0];
    }
  }
  fill(imp, imp + m, false);
  auto toSrc = shortest_path(0, true, true);
  for(int i = 0; i < m; i++) {
    if(imp[i]) {
      del[i] = true;
      auto u = shortest_path(0, true);
      leftSrc[i] = u[l[i]];
      del[i] = false;
    } else {
      leftSrc[i] = toSrc[l[i]]; 
    }
  }
  fill(imp, imp + m, false);
  auto toDes = shortest_path(n - 1, true, true);
  for(int i = 0; i < m; i++) {
    if(imp[i]) {
      del[i] = true;
      auto v = shortest_path(n - 1, true);
      leftDes[i] = v[l[i]];
      del[i] = false;
    } else {
      leftDes[i] = toDes[l[i]];
    }
  }
  long long ans = fromSrc[n - 1] + fromDes[0];
  for(int i = 0; i < m; i++) {
    long long res = c[i];
    res += min(srcRight[i] + w[i] + leftDes[i], srcPath[i]);
    res += min(desRight[i] + w[i] + leftSrc[i], desPath[i]);
    ans = min(ans, res);
  }
  if(ans >= inf) ans = -1;
  cout << ans << endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 384 KB Output is correct
2 Correct 57 ms 384 KB Output is correct
3 Correct 93 ms 504 KB Output is correct
4 Correct 92 ms 504 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 19 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 95 ms 504 KB Output is correct
11 Correct 92 ms 384 KB Output is correct
12 Correct 93 ms 504 KB Output is correct
13 Correct 43 ms 512 KB Output is correct
14 Correct 73 ms 504 KB Output is correct
15 Correct 69 ms 504 KB Output is correct
16 Correct 68 ms 512 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 4600 KB Output is correct
2 Correct 672 ms 4856 KB Output is correct
3 Correct 698 ms 4728 KB Output is correct
4 Correct 98 ms 512 KB Output is correct
5 Correct 80 ms 504 KB Output is correct
6 Correct 28 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 373 ms 4856 KB Output is correct
10 Correct 376 ms 4856 KB Output is correct
11 Correct 548 ms 4744 KB Output is correct
12 Correct 547 ms 4728 KB Output is correct
13 Correct 555 ms 4856 KB Output is correct
14 Correct 538 ms 4984 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 504 KB Output is correct
2 Correct 57 ms 384 KB Output is correct
3 Correct 664 ms 3704 KB Output is correct
4 Correct 60 ms 384 KB Output is correct
5 Correct 866 ms 4760 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 766 ms 5368 KB Output is correct
9 Correct 759 ms 5112 KB Output is correct
10 Incorrect 899 ms 5456 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 384 KB Output is correct
2 Correct 57 ms 384 KB Output is correct
3 Correct 93 ms 504 KB Output is correct
4 Correct 92 ms 504 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 19 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 95 ms 504 KB Output is correct
11 Correct 92 ms 384 KB Output is correct
12 Correct 93 ms 504 KB Output is correct
13 Correct 43 ms 512 KB Output is correct
14 Correct 73 ms 504 KB Output is correct
15 Correct 69 ms 504 KB Output is correct
16 Correct 68 ms 512 KB Output is correct
17 Correct 682 ms 4600 KB Output is correct
18 Correct 672 ms 4856 KB Output is correct
19 Correct 698 ms 4728 KB Output is correct
20 Correct 98 ms 512 KB Output is correct
21 Correct 80 ms 504 KB Output is correct
22 Correct 28 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 373 ms 4856 KB Output is correct
26 Correct 376 ms 4856 KB Output is correct
27 Correct 548 ms 4744 KB Output is correct
28 Correct 547 ms 4728 KB Output is correct
29 Correct 555 ms 4856 KB Output is correct
30 Correct 538 ms 4984 KB Output is correct
31 Correct 94 ms 504 KB Output is correct
32 Correct 57 ms 384 KB Output is correct
33 Correct 664 ms 3704 KB Output is correct
34 Correct 60 ms 384 KB Output is correct
35 Correct 866 ms 4760 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 766 ms 5368 KB Output is correct
39 Correct 759 ms 5112 KB Output is correct
40 Incorrect 899 ms 5456 KB Output isn't correct
41 Halted 0 ms 0 KB -