Submission #1199141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199141		Gray	Swapping Cities (APIO20_swap)	C++20	37 / 100	2095 ms	23912 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define ll long long
#define ln "\n"
using namespace std;
ll n, m;
vector<vector<pair<ll, ll>>> A;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N; m=M; A.resize(n);
    for (ll i=0; i<m; i++){
        A[U[i]].push_back({V[i], W[i]}); A[V[i]].push_back({U[i], W[i]});
    }
}

void dfs(ll u, ll to, vector<ll> &vis, ll &cnt1, ll &cnt2, ll &apos, ll &req, ll hi){
    vis[u]=1; cnt1++; ll cct=0; if (u==to) req=1;
    for (auto &[v, w]:A[u]){
        if (w>hi) continue;
        cnt2++; cct++;
        if (!vis[v]) dfs(v, to, vis, cnt1, cnt2, apos, req, hi);
    }
    if (cct>=3) apos=1;
}

int getMinimumFuelCapacity(int X, int Y) {
    ll l=0, r=2e9; vector<ll> vis(n);
    while (l+1<r){
        ll mid = l+(r-l)/2; vis.assign(n, 0);
        ll cnt1=0, cnt2=0, pos1=0, pos2=0;
        dfs(X, Y, vis, cnt1, cnt2, pos1, pos2, mid);
        if (pos2 and (pos1 or (cnt2/2>=cnt1))){
            r=mid;
        }else l=mid;
    }
    return (r==2e9?-1:r);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27