Submission #414293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414293	2021-05-30T09:59:23 Z	prvocislo	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	29052 KB

swap

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005, inf = 1e9 + 5;
vector<vector<pair<int, int> > > g(maxn);
int n, m;
void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
  n = N, m = M;
  for (int i =0;i < m;i++) g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
}
int d[maxn][maxn];
int getMinimumFuelCapacity(int x, int y) {
  for (int i =0; i < n;i++) for (int j =0;j < n;j++) d[i][j] = inf;
  priority_queue<pair<int, pair<int, int> > > s;
  s.push({0, {x, y}});
  while (!s.empty())
  {
    int u = s.top().second.first, v = s.top().second.second, dist = -s.top().first;
    s.pop();
    if (d[u][v] < dist) continue;
    d[u][v] = dist;
    for (const pair<int, int> &i : g[u])
    {
        int u2 = i.first, d2 = max(dist, i.second);
        if (u2 != v && d[u2][v] == inf) 
          s.push({-d2, {u2, v} });
    }
    for (const pair<int, int> &i : g[v])
    {
        int v2 = i.first, d2 = max(dist, i.second);
        if (v2 != u && d[u][v2] == inf) 
          s.push({-d2, {u, v2} });
    }
  }
  return d[y][x] == inf ? -1 : d[y][x];
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	323 ms	3060 KB	Output is correct
5	Correct	1597 ms	9748 KB	Output is correct
6	Correct	1556 ms	8552 KB	Output is correct
7	Correct	1937 ms	10564 KB	Output is correct
8	Execution timed out	2084 ms	29052 KB	Time limit exceeded

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Runtime error	97 ms	8300 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	323 ms	3060 KB	Output is correct
5	Correct	1597 ms	9748 KB	Output is correct
6	Correct	1556 ms	8552 KB	Output is correct
7	Correct	1937 ms	10564 KB	Output is correct
8	Execution timed out	2084 ms	29052 KB	Time limit exceeded

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	323 ms	3060 KB	Output is correct
5	Correct	1597 ms	9748 KB	Output is correct
6	Correct	1556 ms	8552 KB	Output is correct
7	Correct	1937 ms	10564 KB	Output is correct
8	Execution timed out	2084 ms	29052 KB	Time limit exceeded

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	323 ms	3060 KB	Output is correct
5	Correct	1597 ms	9748 KB	Output is correct
6	Correct	1556 ms	8552 KB	Output is correct
7	Correct	1937 ms	10564 KB	Output is correct
8	Execution timed out	2084 ms	29052 KB	Time limit exceeded

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	323 ms	3060 KB	Output is correct
5	Correct	1597 ms	9748 KB	Output is correct
6	Correct	1556 ms	8552 KB	Output is correct
7	Correct	1937 ms	10564 KB	Output is correct
8	Execution timed out	2084 ms	29052 KB	Time limit exceeded