Submission #414282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414282	2021-05-30T09:54:10 Z	prvocislo	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	25644 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;
  set<pair<int, pair<int, int> > > s;
  s.insert({0, {x, y}});
  while (!s.empty())
  {
    int u = s.begin()->second.first, v = s.begin()->second.second, dist = s.begin()->first;
    s.erase(s.begin());
    if (d[u][v] < dist) continue;
    d[u][v] = dist;
    for (pair<int, int> i : g[u])
    {
        int u2 = i.first, d2 = max(dist, i.second);
        if (u2 != v && d[u2][v] == inf) 
          s.insert({d2, {u2, v} });
    }
    for (pair<int, int> i : g[v])
    {
        int v2 = i.first, d2 = max(dist, i.second);
        if (v2 != u && d[u][v2] == inf) 
          s.insert({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	132 ms	3348 KB	Output is correct
5	Correct	616 ms	10824 KB	Output is correct
6	Correct	701 ms	8752 KB	Output is correct
7	Correct	931 ms	13180 KB	Output is correct
8	Correct	871 ms	8024 KB	Output is correct
9	Runtime error	31 ms	5848 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

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	94 ms	9880 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	132 ms	3348 KB	Output is correct
5	Correct	616 ms	10824 KB	Output is correct
6	Correct	701 ms	8752 KB	Output is correct
7	Correct	931 ms	13180 KB	Output is correct
8	Correct	871 ms	8024 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1703 ms	22012 KB	Output is correct
11	Correct	1898 ms	13932 KB	Output is correct
12	Correct	1898 ms	17664 KB	Output is correct
13	Correct	1301 ms	16960 KB	Output is correct
14	Correct	1571 ms	7884 KB	Output is correct
15	Correct	1820 ms	8196 KB	Output is correct
16	Correct	1763 ms	9152 KB	Output is correct
17	Correct	1803 ms	10692 KB	Output is correct
18	Execution timed out	2036 ms	25644 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	1 ms	332 KB	Output is correct
5	Correct	132 ms	3348 KB	Output is correct
6	Correct	616 ms	10824 KB	Output is correct
7	Correct	701 ms	8752 KB	Output is correct
8	Correct	931 ms	13180 KB	Output is correct
9	Correct	871 ms	8024 KB	Output is correct
10	Runtime error	31 ms	5848 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-

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	132 ms	3348 KB	Output is correct
5	Correct	616 ms	10824 KB	Output is correct
6	Correct	701 ms	8752 KB	Output is correct
7	Correct	931 ms	13180 KB	Output is correct
8	Correct	871 ms	8024 KB	Output is correct
9	Runtime error	31 ms	5848 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

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	1 ms	332 KB	Output is correct
5	Correct	132 ms	3348 KB	Output is correct
6	Correct	616 ms	10824 KB	Output is correct
7	Correct	701 ms	8752 KB	Output is correct
8	Correct	931 ms	13180 KB	Output is correct
9	Correct	871 ms	8024 KB	Output is correct
10	Runtime error	31 ms	5848 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-