oj.uz

Submission #981071

# Submission time Handle Problem Language Result Execution time Memory
981071 2024-05-12T18:54:21 Z Abito Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 37724 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
const int NN=1e3+5;
int n,m,dis[NN][NN];
vector<pair<int,int>> adj[NN];
bool vis[NN][NN];
void dijkstra(int X,int Y){
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) dis[i][j]=INT_MAX,vis[i][j]=0;
    dis[X][Y]=0;
    priority_queue<vector<int>> pq;
    pq.push({0,X,Y});
    while (!pq.empty()){
        int i=pq.top()[1],j=pq.top()[2];
        pq.pop();
        if (vis[i][j]) continue;
        for (auto u:adj[i]){
            if (u.F==j) continue;
            int d=max(dis[i][j],u.S);
            if (d<dis[u.F][j]){
                dis[u.F][j]=d;
                pq.push({-d,u.F,j});
            }
        }
        for (auto u:adj[j]){
            if (u.F==i) continue;
            int d=max(dis[i][j],u.S);
            if (d<dis[i][u.F]){
                dis[i][u.F]=d;
                pq.push({-d,i,u.F});
            }
        }
    }return;
}
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++){
        adj[U[i]].pb({V[i],W[i]});
        adj[V[i]].pb({U[i],W[i]});
    }
    return;
}

int getMinimumFuelCapacity(int X, int Y) {
    dijkstra(X,Y);
    /*for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cout<<dis[i][j]<<' ';
        }cout<<endl;
    }*/
    if (dis[Y][X]==INT_MAX) return -1;
    return dis[Y][X];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 88 ms 6024 KB Output is correct
5 Correct 383 ms 11616 KB Output is correct
6 Correct 445 ms 11296 KB Output is correct
7 Correct 562 ms 17124 KB Output is correct
8 Correct 512 ms 9176 KB Output is correct
9 Runtime error 95 ms 17304 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 126 ms 24824 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 88 ms 6024 KB Output is correct
5 Correct 383 ms 11616 KB Output is correct
6 Correct 445 ms 11296 KB Output is correct
7 Correct 562 ms 17124 KB Output is correct
8 Correct 512 ms 9176 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1134 ms 26636 KB Output is correct
11 Correct 1110 ms 16892 KB Output is correct
12 Correct 1166 ms 19308 KB Output is correct
13 Correct 827 ms 18048 KB Output is correct
14 Correct 918 ms 12744 KB Output is correct
15 Correct 1159 ms 9920 KB Output is correct
16 Correct 1094 ms 11780 KB Output is correct
17 Correct 1086 ms 12900 KB Output is correct
18 Correct 1475 ms 25936 KB Output is correct
19 Correct 871 ms 20860 KB Output is correct
20 Correct 1174 ms 17692 KB Output is correct
21 Execution timed out 2041 ms 37724 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 88 ms 6024 KB Output is correct
6 Correct 383 ms 11616 KB Output is correct
7 Correct 445 ms 11296 KB Output is correct
8 Correct 562 ms 17124 KB Output is correct
9 Correct 512 ms 9176 KB Output is correct
10 Runtime error 95 ms 17304 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 88 ms 6024 KB Output is correct
5 Correct 383 ms 11616 KB Output is correct
6 Correct 445 ms 11296 KB Output is correct
7 Correct 562 ms 17124 KB Output is correct
8 Correct 512 ms 9176 KB Output is correct
9 Runtime error 95 ms 17304 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 88 ms 6024 KB Output is correct
6 Correct 383 ms 11616 KB Output is correct
7 Correct 445 ms 11296 KB Output is correct
8 Correct 562 ms 17124 KB Output is correct
9 Correct 512 ms 9176 KB Output is correct
10 Runtime error 95 ms 17304 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -