Submission #428996

#	Time	Username	Problem	Language	Result	Execution time	Memory
428996		proma	Swapping Cities (APIO20_swap)	C++17	17 / 100	2076 ms	14764 KiB

swap

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int MAX = 1e5+5;

int n, m, used[MAX];
vector <pair <int, int>> g[MAX];

void init (int N, int M, vector <int> U, vector <int> V, vector <int> W) {
    n = N;
    m = M;
    int inf = 0;
    for (int i = 0; i < M; i ++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
}

void dfs (int v, int p, int k, int& flag){
    used[v] = 1;
    int deg = 0;
    for (auto i: g[v]) {
        if (i.second <= k and i.first != p and used[i.first] == 1)
            flag = 1;
        if (i.second <= k and !used[i.first])
            dfs(i.first, v, k, flag);
        if (i.second <= k)
            deg ++;
    }
    if (deg >= 3) flag = 1;
    used[v] = 2;
}

bool isPossible (int a, int b, int k) {
    memset(used, 0, sizeof(used));
    int flag = 0;
    dfs(a, -1, k, flag);
    if (flag and used[b]) return true;
    else return false;
}

int getMinimumFuelCapacity (int X, int Y) {
    int l = 1, r = 1e9, best = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (isPossible(X, Y, mid)) {
            best = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return best;
}

Compilation message (stderr)

swap.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
swap.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:17:9: warning: unused variable 'inf' [-Wunused-variable]
   17 |     int inf = 0;
      |         ^~~

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