oj.uz

Submission #1054360

# Submission time Handle Problem Language Result Execution time Memory
1054360 2024-08-12T09:07:43 Z Kipras Swapping Cities (APIO20_swap) C++17
0 / 100
 50 ms 15052 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 444 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 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 19 ms 9024 KB Output is correct
10 Correct 29 ms 10444 KB Output is correct
11 Correct 23 ms 9928 KB Output is correct
12 Correct 23 ms 10916 KB Output is correct
13 Correct 23 ms 10436 KB Output is correct
14 Correct 21 ms 9672 KB Output is correct
15 Correct 49 ms 14156 KB Output is correct
16 Correct 50 ms 13940 KB Output is correct
17 Correct 50 ms 14288 KB Output is correct
18 Correct 50 ms 15052 KB Output is correct
19 Incorrect 26 ms 5968 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 46 ms 13304 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 444 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 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 348 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 348 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 444 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 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 19 ms 9024 KB Output is correct
10 Correct 29 ms 10444 KB Output is correct
11 Correct 23 ms 9928 KB Output is correct
12 Correct 23 ms 10916 KB Output is correct
13 Correct 23 ms 10436 KB Output is correct
14 Correct 21 ms 9672 KB Output is correct
15 Correct 49 ms 14156 KB Output is correct
16 Correct 50 ms 13940 KB Output is correct
17 Correct 50 ms 14288 KB Output is correct
18 Correct 50 ms 15052 KB Output is correct
19 Incorrect 46 ms 13304 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -