oj.uz

Submission #981069

# Submission time Handle Problem Language Result Execution time Memory
981069 2024-05-12T18:52:06 Z Abito Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 37624 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]){
            for (auto v:adj[j]){
                if (u.F==j && v.F==i) continue;
                if (u.F==v.F) continue;
                int d=max(dis[i][j],max(u.S,v.S));
                if (d<dis[u.F][v.F]){
                    dis[u.F][v.F]=d;
                    pq.push({-d,u.F,v.F});
                }
            }
        }
        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 111 ms 6244 KB Output is correct
5 Correct 482 ms 12308 KB Output is correct
6 Correct 499 ms 12136 KB Output is correct
7 Correct 664 ms 15840 KB Output is correct
8 Correct 621 ms 9156 KB Output is correct
9 Runtime error 77 ms 17572 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 116 ms 24940 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 111 ms 6244 KB Output is correct
5 Correct 482 ms 12308 KB Output is correct
6 Correct 499 ms 12136 KB Output is correct
7 Correct 664 ms 15840 KB Output is correct
8 Correct 621 ms 9156 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1261 ms 27524 KB Output is correct
11 Correct 1338 ms 16360 KB Output is correct
12 Correct 1429 ms 19324 KB Output is correct
13 Correct 975 ms 17536 KB Output is correct
14 Correct 1088 ms 12044 KB Output is correct
15 Correct 1328 ms 10124 KB Output is correct
16 Correct 1272 ms 12312 KB Output is correct
17 Correct 1222 ms 13960 KB Output is correct
18 Correct 1676 ms 26500 KB Output is correct
19 Correct 1323 ms 31960 KB Output is correct
20 Correct 1379 ms 18756 KB Output is correct
21 Execution timed out 2066 ms 37624 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 111 ms 6244 KB Output is correct
6 Correct 482 ms 12308 KB Output is correct
7 Correct 499 ms 12136 KB Output is correct
8 Correct 664 ms 15840 KB Output is correct
9 Correct 621 ms 9156 KB Output is correct
10 Runtime error 77 ms 17572 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 111 ms 6244 KB Output is correct
5 Correct 482 ms 12308 KB Output is correct
6 Correct 499 ms 12136 KB Output is correct
7 Correct 664 ms 15840 KB Output is correct
8 Correct 621 ms 9156 KB Output is correct
9 Runtime error 77 ms 17572 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 111 ms 6244 KB Output is correct
6 Correct 482 ms 12308 KB Output is correct
7 Correct 499 ms 12136 KB Output is correct
8 Correct 664 ms 15840 KB Output is correct
9 Correct 621 ms 9156 KB Output is correct
10 Runtime error 77 ms 17572 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -