Submission #395285

#	Time	Username	Problem	Language	Result	Execution time	Memory
395285		abc864197532	Swapping Cities (APIO20_swap)	C++17	17 / 100	2101 ms	23180 KiB

swap

#include <bits/stdc++.h>
// #include "grader_swap.cpp"
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, Doludu = 123, N = 100001, logN = 18, K = 40;

vector <pii> adj[N], out_of_tree[N];
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) {
        adj[u[i]].eb(v[i], w[i]);
        adj[v[i]].eb(u[i], w[i]);
    }
}


bool vis[N], cyc;
int cnt[N], mx;

void dfs(int v, int pa, int goal, int bound) {
    vis[v] = true;
    for (auto [u, w] : adj[v]) if (u != pa && w <= bound) {
        if (vis[u]) cyc = true;
        else cnt[v]++, cnt[u]++, mx = max({mx, cnt[v], cnt[u]}), dfs(u, v, goal, bound);
    }
}

int getMinimumFuelCapacity(int u, int v) {
    int l = 0, r = 1 << 30;
    while (r - l > 1) {
        int mid = l + r >> 1;
        for (int i = 0; i < n; ++i) vis[i] = false, cnt[i] = 0;
        cyc = false, mx = 0;
        dfs(u, -1, v, mid);
        if (vis[v] && (cyc || mx > 2)) r = mid;
        else l = mid;
    }
    if (r == 1 << 30) r = -1;
    return r;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
2 3 3
1 4 10
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2
 */

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = l + r >> 1;
      |                   ~~^~~

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