Submission #428990

#	Time	Username	Problem	Language	Result	Execution time	Memory
428990		proma	Swapping Cities (APIO20_swap)	C++17	17 / 100	2091 ms	16304 KiB

swap

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5+5;
const int INF = 1e9;

int n, m, used[MAX];
vector <pair <int, int>> g[MAX];

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 ++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
}

void dfs (int v, int p, int k, int& flag){
    used[v] = 1;
    int deg = 0;
    for (auto i: g[v]) {
        if (i.second <= k and i.first != p and used[i.first] == 1)
            flag = 1;
        if (i.second <= k and !used[i.first])
            dfs(i.first, v, k, flag);
        if (i.second <= k)
            deg ++;
    }
    if (deg >= 3) flag = 1;
    used[v] = 2;
}

bool isPossible (int a, int b, int k) {
    memset(used, 0, sizeof(used));
    int flag = 0;
    dfs(a, -1, k, flag);
    if (flag and used[b]) return true;
    else return false;
}

int getMinimumFuelCapacity (int X, int Y) {
    int l = 1, r = INF, best = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (isPossible(X, Y, mid)) {
            best = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return best;
}

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