oj.uz

Submission #1054401

# Submission time Handle Problem Language Result Execution time Memory
1054401 2024-08-12T09:38:40 Z Kipras Swapping Cities (APIO20_swap) C++17
0 / 100
 71 ms 18604 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<ll> adj[maxN];
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, bool is){
    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];

    if(is) {
        if(cycle[a]==0)cycle[a]=t;
        if(cycle[b]==0)cycle[b]=t;
    }

    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;
        adj[v].push_back(u);
        adj[u].push_back(v);
        bool is = 0;
        if(adj[v].size()>2||adj[u].size()>2)is=1;
        unite(v, u, w, is);
    }
}

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 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 28 ms 12748 KB Output is correct
10 Correct 34 ms 14444 KB Output is correct
11 Correct 39 ms 14368 KB Output is correct
12 Correct 32 ms 14972 KB Output is correct
13 Correct 31 ms 14884 KB Output is correct
14 Correct 28 ms 12992 KB Output is correct
15 Correct 63 ms 17380 KB Output is correct
16 Correct 67 ms 17096 KB Output is correct
17 Correct 71 ms 18248 KB Output is correct
18 Correct 60 ms 18604 KB Output is correct
19 Incorrect 29 ms 9512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Incorrect 56 ms 17208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 28 ms 12748 KB Output is correct
10 Correct 34 ms 14444 KB Output is correct
11 Correct 39 ms 14368 KB Output is correct
12 Correct 32 ms 14972 KB Output is correct
13 Correct 31 ms 14884 KB Output is correct
14 Correct 28 ms 12992 KB Output is correct
15 Correct 63 ms 17380 KB Output is correct
16 Correct 67 ms 17096 KB Output is correct
17 Correct 71 ms 18248 KB Output is correct
18 Correct 60 ms 18604 KB Output is correct
19 Incorrect 56 ms 17208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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