oj.uz

Submission #1054498

# Submission time Handle Problem Language Result Execution time Memory
1054498 2024-08-12T10:19:08 Z Kipras Swapping Cities (APIO20_swap) C++17
6 / 100
 196 ms 16932 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//#include "swap.h"

const ll maxN = 1e5+10;
const ll inf = 1e18;

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(par[node]==node)return node;
    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]=min(cycle[a], t);
        cycle[b]=min(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 = 0; i <= n; i++) {
        par[i]=i;
        sz[i]=1;
        cycle[i]=inf;
        timeP[i]=inf;
    }
    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 = 1e15;
    while(l < h && l < 1e10) {
        ll m = (l+h)/2;
        ll v1 = find(X, m), v2 = find(Y, m);
        //cout<<m<<" "<<X<<" "<<Y<<" "<<l<<" "<<h<<" "<<v1<<" "<<v2<<" "<<cycle[v1]<<" "<<cycle[v2]<<"\n";
        if(v1==v2&&cycle[v1]<=m) {
            h=m;
        }else l = m+1;
    }
    if(h>1e10) {
        return -1;
    }else return l;
}


/*

5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
3
1 2
2 4
0 1


3 2
0 0
1 2
5 5
1
1 2


*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4712 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 33 ms 11732 KB Output is correct
10 Correct 33 ms 13140 KB Output is correct
11 Correct 31 ms 13256 KB Output is correct
12 Correct 33 ms 14000 KB Output is correct
13 Correct 30 ms 13572 KB Output is correct
14 Correct 30 ms 11972 KB Output is correct
15 Correct 70 ms 15356 KB Output is correct
16 Correct 69 ms 14964 KB Output is correct
17 Correct 69 ms 15396 KB Output is correct
18 Correct 60 ms 15976 KB Output is correct
19 Correct 100 ms 9552 KB Output is correct
20 Correct 189 ms 16208 KB Output is correct
21 Correct 196 ms 16252 KB Output is correct
22 Correct 189 ms 16932 KB Output is correct
23 Correct 102 ms 16764 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4712 KB Output is correct
3 Incorrect 58 ms 16228 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 4696 KB Output is correct
2 Correct 1 ms 4712 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 1 ms 4696 KB Output is correct
10 Incorrect 1 ms 4700 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 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4712 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 1 ms 4700 KB Output is correct
10 Correct 33 ms 11732 KB Output is correct
11 Correct 33 ms 13140 KB Output is correct
12 Correct 31 ms 13256 KB Output is correct
13 Correct 33 ms 14000 KB Output is correct
14 Correct 30 ms 13572 KB Output is correct
15 Incorrect 1 ms 4700 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 4696 KB Output is correct
2 Correct 1 ms 4712 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 33 ms 11732 KB Output is correct
10 Correct 33 ms 13140 KB Output is correct
11 Correct 31 ms 13256 KB Output is correct
12 Correct 33 ms 14000 KB Output is correct
13 Correct 30 ms 13572 KB Output is correct
14 Correct 30 ms 11972 KB Output is correct
15 Correct 70 ms 15356 KB Output is correct
16 Correct 69 ms 14964 KB Output is correct
17 Correct 69 ms 15396 KB Output is correct
18 Correct 60 ms 15976 KB Output is correct
19 Incorrect 58 ms 16228 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4712 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 1 ms 4700 KB Output is correct
10 Correct 33 ms 11732 KB Output is correct
11 Correct 33 ms 13140 KB Output is correct
12 Correct 31 ms 13256 KB Output is correct
13 Correct 33 ms 14000 KB Output is correct
14 Correct 30 ms 13572 KB Output is correct
15 Correct 30 ms 11972 KB Output is correct
16 Correct 70 ms 15356 KB Output is correct
17 Correct 69 ms 14964 KB Output is correct
18 Correct 69 ms 15396 KB Output is correct
19 Correct 60 ms 15976 KB Output is correct
20 Incorrect 58 ms 16228 KB Output isn't correct
21 Halted 0 ms 0 KB -