Submission #1199067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199067		Gray	Swapping Cities (APIO20_swap)	C++20	0 / 100	2093 ms	22860 KiB

swap

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

ll n, m;
vector<array<ll, 3>> e;
vector<ll> enabled;
vector<vector<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); e.resize(m);
    for (ll i=0; i<m; i++){
        e[i] = {U[i], V[i], W[i]};
        A[U[i]].push_back(i); A[V[i]].push_back(i);
    }
}

void dfs(ll u, ll to, vector<ll> &vis, vector<ll> &st, vector<ll> &res){
    st.push_back(u); vis[u]=1;
    if (u==to) res=st;
    for (auto i:A[u]){
        ll v = e[i][0]^e[i][1]^u;
        if (!enabled[i]) continue;
        if (!vis[v]) dfs(v, to, vis, st, res);
    }
    st.pop_back();
}
void dfs2(ll u, vector<ll> &dp){
    ll my = 0; dp[u]=0;
    for (auto i:A[u]){
        ll v = e[i][0]^e[i][1]^u;
        if (!enabled[i]) continue;
        if (dp[v]==-1) dfs2(v, dp);
        my+=dp[v];
    }
    dp[u]=my;
}

int getMinimumFuelCapacity(int X, int Y) {
    ll l=0, r=2e9; vector<ll> vis(n);
    set<ll> avail;
    while (l+1<r){
        ll mid = (l+r)/2;
        enabled.assign(m, 0); vis.assign(n, 0);
        for (ll i=0; i<m; i++){
            if (e[i][2]<=mid) enabled[i]=1;
        }
        vector<ll> res, temp, dp(n, -1); dp[Y]=1;
        dfs(X, Y, vis, temp, res);
        avail.clear(); for (auto v:res) avail.insert(v);
        for (ll i=1; i<(ll)res.size()-1; i++){
            dp[res[i]]=0;
        }
        dfs2(X, dp);
        bool pos=0;
        for (ll i=1; i<(ll)res.size()-1; i++){
            if (A[i].size()>2) pos=1;
        }
        if ((pos or dp[X]>1) and (X!=Y)) r=mid;
        else l=mid;
    }
    return (r==2e9?-1:r);
}

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