Submission #407132

#	Time	Username	Problem	Language	Result	Execution time	Memory
407132		Maqsut_03	Swapping Cities (APIO20_swap)	C++14	0 / 100	2 ms	2636 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;


int n, m;
std::vector<int> e[N];
std::vector<int> U, V, W, v;
std::vector<int> p;

std::vector<bool> vis;
bool have;

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;
    v = W;
    sort(v.begin(), v.end());
}


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];
    }
    std::vector<bool> bad(n, false);
    for (auto x : got)  bad[x] = true;

    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]]) 
		{
            e[U[i]].emplace_back(V[i]);
            e[V[i]].emplace_back(U[i]);
        }
    }
    
	if (!got.size()) 
	{
        e[X].erase(find(e[X].begin(), e[X].end(), Y));
        e[Y].erase(find(e[Y].begin(), e[Y].end(), X));
    }

    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) 
{
    int l = 0, r = v.size() - 1;
    while (l < r) 
	{
        int mid = (l + r) / 2;
        if (check(X, Y, v[mid]))  r = mid;
        else l = mid + 1;
    }
    
	if (r == v.size()) return -1;
    return v[r];
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:103:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  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