Submission #724192

#	Time	Username	Problem	Language	Result	Execution time	Memory
724192		danikoynov	Swapping Cities (APIO20_swap)	C++14	17 / 100	2077 ms	24520 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int v, u, w;
};

const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;


vector < edge > g[maxn];
int n, m;

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 ++)
    {
        edge e;
        e.u = V[i];
        e.w = W[i];
        g[U[i]].push_back(e);
        e.u = U[i];
        g[V[i]].push_back(e);
    }
}

int used[maxn], deg[maxn], edge_cnt;

void dfs(int v, int lim)
{
    used[v] = 1;
    for (edge nb : g[v])
    {
        if (nb.w > lim)
            continue;
        edge_cnt ++;
        deg[v] ++;
        if (used[nb.u])
            continue;
        dfs(nb.u, lim);
    }
}
bool check(int x, int y, int fuel)
{
    for (int i = 0; i < n; i ++)
    {
        used[i] = deg[i] = 0;
    }
    edge_cnt = 0;
    dfs(x, fuel);

    if (!used[y])
        return false;

    edge_cnt /= 2;
    int used_ver = 0;
    bool deg3 = false;
    for (int i = 0; i < n; i ++)
    {
        used_ver += used[i];
        if (deg[i] > 2)
            deg3 = true;
    }
    if (edge_cnt >= used_ver || deg3)
        return true;
    return false;
}
int getMinimumFuelCapacity(int X, int Y)
{
    int left = 0, right = inf;
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if (check(X, Y, mid))
            right = mid - 1;
        else
            left = mid + 1;
    }

    if (left > inf)
        return - 1;
    return left;
}

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