oj.uz

Submission #1054361

# Submission time Handle Problem Language Result Execution time Memory
1054361 2024-08-12T09:08:09 Z Kipras Swapping Cities (APIO20_swap) C++17
0 / 100
 92 ms 10032 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include "swap.h"

const ll maxN = 1e5+10;

ll par[maxN], timeP[maxN], cycle[maxN], sz[maxN];
ll n, m;
vector<pair<ll, pair<ll, ll>>> edges;

ll find(ll node, ll t) {
    if(timeP[node]>=t) {
        return find(par[node], t);
    }
    return node;
}

void unite(ll a, ll b, ll t){
    a = find(a, t);
    b = find(b, t);
    if(a==b){
        cycle[a]=t;
        cycle[b]=t;
        return;
    }
    if(sz[a]>sz[b]) {
        swap(a, b);
    }
    if(cycle[a]==0&&cycle[b]!=0)
        cycle[a]=cycle[b];
    else if(cycle[b]==0&&cycle[a]!=0)
        cycle[b]=cycle[a];
    sz[b]+=sz[a];
    par[a]=b;
    timeP[a]=t;
}

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++) {
        edges.push_back({W[i], {U[i], V[i]}});
    }
    for(int i = 1; i <= n; i++) {
        par[i]=i;
        sz[i]=1;
    }
    sort(edges.begin(), edges.end());
    for(auto i : edges) {
        ll v = i.second.first, u = i.second.second;
        ll w = i.first;
        unite(v, u, w);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    ll l = 0, h = 1e18;
    while(l < h && l < 1e10) {
        ll m = (l+h)/2;
        ll v1 = find(X, m), v2 = find(Y, m);
        if(v1==v2&&cycle[v1]<=m) {
            h=l;
        }else l = h+1;
    }
    if(h>1e10) {
        return -1;
    }else return l;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 18 ms 6872 KB Output is correct
10 Correct 22 ms 8136 KB Output is correct
11 Correct 37 ms 8396 KB Output is correct
12 Correct 23 ms 8396 KB Output is correct
13 Correct 22 ms 8392 KB Output is correct
14 Correct 35 ms 7756 KB Output is correct
15 Correct 92 ms 9808 KB Output is correct
16 Correct 50 ms 9588 KB Output is correct
17 Correct 58 ms 10028 KB Output is correct
18 Correct 90 ms 10032 KB Output is correct
19 Incorrect 25 ms 3928 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 45 ms 9408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 18 ms 6872 KB Output is correct
10 Correct 22 ms 8136 KB Output is correct
11 Correct 37 ms 8396 KB Output is correct
12 Correct 23 ms 8396 KB Output is correct
13 Correct 22 ms 8392 KB Output is correct
14 Correct 35 ms 7756 KB Output is correct
15 Correct 92 ms 9808 KB Output is correct
16 Correct 50 ms 9588 KB Output is correct
17 Correct 58 ms 10028 KB Output is correct
18 Correct 90 ms 10032 KB Output is correct
19 Incorrect 45 ms 9408 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -