oj.uz

Submission #981683

# Submission time Handle Problem Language Result Execution time Memory
981683 2024-05-13T12:56:30 Z Alkaser_ID Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 8648 KB 
#include "swap.h"
using namespace std;
#include <bits/stdc++.h>

vector<vector<int>> adj[100005];
int n,m;
vector<pair<int,pair<int,int>>> v;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;m = M;
    for(int i=0;i<m;++i){
        v.push_back({W[i],{U[i],V[i]}});
    }
    sort(v.begin(),v.end());
}
int p[100005],sz[100005]; bool bl[100005];
inline int parent(int a){
    if(a == p[a]) return a;
    return a = parent(p[a]);
}

inline void merg(int x,int y){
    int a = parent(x),b = parent(y);
    if(a == b) return;
    if(sz[b] > sz[a]) swap(a,b);
    sz[a] += sz[b];
    p[b] = a;
    bl[a] = bl[a] | bl[b];
}

int getMinimumFuelCapacity(int X, int Y) {
    for(int i=0;i<n;++i) {
        p[i] = i; sz[i] = 1;
        bl[i] = false;
    }
    int res = -1;
    for(int i=0;i<m;++i){
        int vl = v[i].first;
        int u = v[i].second.first, d = v[i].second.second;
        u = parent(u);d = parent(d);
        if(u == d) bl[u] = true;
        else merg(u,d);
        int px = parent(X),py = parent(Y);
        if(px == py && bl[px]) {
            res = vl;
            break;
        }
    }
    return res;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 29 ms 6868 KB Output is correct
10 Correct 39 ms 7380 KB Output is correct
11 Correct 39 ms 7376 KB Output is correct
12 Correct 42 ms 7372 KB Output is correct
13 Correct 38 ms 7380 KB Output is correct
14 Execution timed out 2028 ms 7116 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Execution timed out 2009 ms 8648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Incorrect 2 ms 3420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 29 ms 6868 KB Output is correct
11 Correct 39 ms 7380 KB Output is correct
12 Correct 39 ms 7376 KB Output is correct
13 Correct 42 ms 7372 KB Output is correct
14 Correct 38 ms 7380 KB Output is correct
15 Incorrect 2 ms 3420 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 29 ms 6868 KB Output is correct
10 Correct 39 ms 7380 KB Output is correct
11 Correct 39 ms 7376 KB Output is correct
12 Correct 42 ms 7372 KB Output is correct
13 Correct 38 ms 7380 KB Output is correct
14 Execution timed out 2028 ms 7116 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 1 ms 3420 KB Output is correct
10 Correct 29 ms 6868 KB Output is correct
11 Correct 39 ms 7380 KB Output is correct
12 Correct 39 ms 7376 KB Output is correct
13 Correct 42 ms 7372 KB Output is correct
14 Correct 38 ms 7380 KB Output is correct
15 Execution timed out 2028 ms 7116 KB Time limit exceeded
16 Halted 0 ms 0 KB -