oj.uz

Submission #981938

# Submission time Handle Problem Language Result Execution time Memory
981938 2024-05-13T16:49:55 Z Abito Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 57180 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[5][NN][NN],q;
vector<pair<int,int>> adj[NN];
bool vis[5][NN][NN];
void dijkstra(int X,int Y){
    dis[q][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[q][i][j]) continue;
        vis[q][i][j]=1;
        for (auto u:adj[i]){
            if (u.F==j) continue;
            int d=max(dis[q][i][j],u.S);
            if (d<dis[q][u.F][j] || dis[q][u.F][j]<0){
                dis[q][u.F][j]=d;
                pq.push({-d,u.F,j});
            }
        }
        for (auto u:adj[j]){
            if (u.F==i) continue;
            int d=max(dis[q][i][j],u.S);
            if (d<dis[q][i][u.F] || dis[q][i][u.F]<0){
                dis[q][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]});
    }
    memset(dis,-1,sizeof(dis));
    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;
    }*/
    return dis[q++][Y][X];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20672 KB Output is correct
4 Correct 93 ms 24300 KB Output is correct
5 Correct 395 ms 30404 KB Output is correct
6 Correct 430 ms 30632 KB Output is correct
7 Correct 576 ms 34532 KB Output is correct
8 Correct 540 ms 28928 KB Output is correct
9 Runtime error 47 ms 48820 KB Execution killed with signal 7
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Runtime error 77 ms 56172 KB Execution killed with signal 7
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20672 KB Output is correct
4 Correct 93 ms 24300 KB Output is correct
5 Correct 395 ms 30404 KB Output is correct
6 Correct 430 ms 30632 KB Output is correct
7 Correct 576 ms 34532 KB Output is correct
8 Correct 540 ms 28928 KB Output is correct
9 Correct 5 ms 20824 KB Output is correct
10 Correct 1131 ms 43416 KB Output is correct
11 Correct 1180 ms 34992 KB Output is correct
12 Correct 1199 ms 38808 KB Output is correct
13 Correct 846 ms 36592 KB Output is correct
14 Correct 940 ms 32044 KB Output is correct
15 Correct 1163 ms 28680 KB Output is correct
16 Correct 1151 ms 32320 KB Output is correct
17 Correct 1090 ms 31144 KB Output is correct
18 Correct 1433 ms 45192 KB Output is correct
19 Correct 868 ms 39808 KB Output is correct
20 Correct 1179 ms 39276 KB Output is correct
21 Execution timed out 2060 ms 57180 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 3 ms 20824 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 4 ms 20672 KB Output is correct
5 Correct 93 ms 24300 KB Output is correct
6 Correct 395 ms 30404 KB Output is correct
7 Correct 430 ms 30632 KB Output is correct
8 Correct 576 ms 34532 KB Output is correct
9 Correct 540 ms 28928 KB Output is correct
10 Runtime error 47 ms 48820 KB Execution killed with signal 7
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20672 KB Output is correct
4 Correct 93 ms 24300 KB Output is correct
5 Correct 395 ms 30404 KB Output is correct
6 Correct 430 ms 30632 KB Output is correct
7 Correct 576 ms 34532 KB Output is correct
8 Correct 540 ms 28928 KB Output is correct
9 Runtime error 47 ms 48820 KB Execution killed with signal 7
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 3 ms 20824 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 4 ms 20672 KB Output is correct
5 Correct 93 ms 24300 KB Output is correct
6 Correct 395 ms 30404 KB Output is correct
7 Correct 430 ms 30632 KB Output is correct
8 Correct 576 ms 34532 KB Output is correct
9 Correct 540 ms 28928 KB Output is correct
10 Runtime error 47 ms 48820 KB Execution killed with signal 7
11 Halted 0 ms 0 KB -