Submission #878283

#	Time	Username	Problem	Language	Result	Execution time	Memory
878283		boris_mihov	Swapping Cities (APIO20_swap)	C++17	0 / 100	2063 ms	13084 KiB

swap

#include "swap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
 
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;
 
int n, m;
bool vis[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
 
int dfs(int node, int par, int dist)
{
    int res = 2;
    vis[node] = true;
    for (const auto &[u, d] : g[node])
    {
        if (d > dist) 
        {
            continue;
        }

        res--;
        if (vis[u])
        {
            continue;
        }
 
        res += dfs(u, node, dist);
    }
    
    return res;
}

void clearDFS(int node)
{
    vis[node] = false;
    for (const auto &[u, d] : g[node])
    {
        if (vis[u])
        {
            clearDFS(u);
        }
    }
}
 
bool check(int u, int v, int dist)
{
    bool res = (dfs(u, 0, dist) <= 0) && vis[v];
    clearDFS(u);
    return res;
}
 
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) 
{
    n = N; m = M;
    for (int i = 0 ; i < M ; ++i)
    {
        U[i]++; V[i]++;
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
}
 
int getMinimumFuelCapacity(int x, int y) 
{
    x++; y++;
    int l = 0, r = INF + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(x, y, mid)) l = mid;
        else r = mid;
    }
 
    if (r > INF) return -1;
    return 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