Submission #406090

#	Time	Username	Problem	Language	Result	Execution time	Memory
406090		tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2092 ms	14116 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;
std::vector<int> e[N];
std::vector<int> U, V, W;
int n, m;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    ::U = U;
    ::V = V;
    ::W = W;
    ::n = n;
    ::m = m;
}
std::vector<int> p;
std::vector<bool> vis;
bool have;
void dfs(int u, int P) {
    p[u] = P;
    vis[u] = true;
    if (e[u].size() > 2) have = true;
    for (auto v : e[u]) {
        if (!vis[v]) {
            dfs(v, u);
        }
    }
}
bool check(int X, int Y, int mid) {
    for (int i = 0; i < n; i++) e[i].clear();
    for (int i = 0; i < m; i++) {
        if (W[i] <= mid) {
            e[U[i]].emplace_back(V[i]);
            e[V[i]].emplace_back(U[i]);
        }
    }
    p.assign(n, -1);
    vis.assign(n, false);
    have = false;
    dfs(X, -1);
    if (p[Y] == -1)
        return false;
    if (have) {
        return true;
    }
    int y = Y;
    std::vector<int> got;
    y = p[y];
    while (y != -1 && p[y] != -1) {
        got.push_back(y);
        y = p[y];
    }
    y = Y;
    std::vector<bool> bad(n);
    for (auto x : got) {
        bad[x] = true;
        y = x;
    }
    for (int i = 0; i < n; i++) e[i].clear();
    for (int i = 0; i < m; i++) {
        if (W[i] <= mid && !bad[U[i]] && !bad[V[i]]
         && !((U[i] == X && V[i] == Y) || (U[i] == Y && V[i] == X))) {
            e[U[i]].emplace_back(V[i]);
            e[V[i]].emplace_back(U[i]);
        }
    }
    p.assign(n, -1);
    vis.assign(n, false);
    dfs(X, -1);
    if (p[Y] != -1)
        return true;
    return false;
}
int getMinimumFuelCapacity(int X, int Y) {
    std::vector<int> v = W;
    sort(v.begin(), v.end());
    int l = -1, r = v.size();
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(X, Y, v[mid])) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (r == v.size()) return -1;
    return v[r];
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:84:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (r == v.size()) return -1;
      |         ~~^~~~~~~~~~~

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