Submission #1054498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054498		Kipras	Swapping Cities (APIO20_swap)	C++17	6 / 100	196 ms	16932 KiB

swap

#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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27