Submission #1164304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164304		Otalp	Swapping Cities (APIO20_swap)	C++20	37 / 100	2095 ms	19448 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

vector<pii> q[200100];
int pos[200100];
vector<int> h;
int n, m;

void dfs(int v, int cl){
    pos[v] = 1;
    int sz = 0;
    for(pii e: q[v]){
        int to = e.ff;
        int w = e.ss;
        if(w > cl) continue;
        sz ++;
        if(pos[to]) continue;
        dfs(to, cl);
    }
    h.pb(sz);
}

bool check(int k, int x, int y){
    h.clear();
    for(int i=0; i<n; i++){
        pos[i] = 0;
    }
    dfs(x, k);
    if(!pos[y]) return 0;
    int ok = 0;
    int cnt = 0;
    for(int x: h){
        if(x == 1) cnt++;
        if(x > 2) ok = 1;
    }
    return (cnt != 2 or ok);
}

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++){
        int l = U[i], r = V[i], x = W[i];
        q[l].pb({r, x});
        q[r].pb({l, x});
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int l=1, r=1e9 + 1;
    if(!check(r, X, Y)) return -1;
    while(l < r){
        int mid = (l + r)/2;
        if(check(mid, X, Y)) r = mid;
        else l = mid + 1;
    }
    return 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