Submission #409697

#	Time	Username	Problem	Language	Result	Execution time	Memory
409697		kwongweng	Swapping Cities (APIO20_swap)	C++17	100 / 100	391 ms	22348 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second

vector<pair<int, ii> > edges;
int n, m;
vi p(100001), sz(100001, 1), s(100001), e(100001), line(100001, -1), sub(100001);
vi d(100001), g[100001];

int get(int a){
    if (p[a] == a) return a;
    return get(p[a]);
}

void Union(int a, int b, int w){
    int c = get(a); int d = get(b);
    if (c == d){
        if (line[c] == -1) line[c] = w;
        return;
    }
    if (sz[c] < sz[d]){
        swap(c, d); swap(a, b);
    }
    p[d] = c;
    sz[c] += sz[d];
    sub[d] = w;
    if (line[c] == -1 && line[d] == -1){
        if (s[c] == a && b == s[d]){
            s[c] = e[d]; return;
        }
        if (s[c] == a && b == e[d]){
            s[c] = s[d]; return;
        }
        if (e[c] == a && b == s[d]){
            e[c] = e[d]; return;
        }
        if (e[c] == a && b == e[d]){
            e[c] = s[d]; return;
        }
        line[c] = w; return;
    }
    if (line[c] == -1) line[c] = w;
}

void init(int N, int M, vi U, vi V, vi W) {
    n = N; m = M;
    FOR(i, 0, m){
        edges.pb({W[i], {U[i], V[i]}});
    }
    FOR(i, 0, n){
        p[i] = i;
        s[i] = i;
        e[i] = i;
    }
    sort(edges.begin(), edges.end());
    FOR(i, 0, m){
        Union(edges[i].S.F, edges[i].S.S, edges[i].F);
    }
    int head;
    FOR(i, 0, n){
        if (p[i] != i){
            g[p[i]].pb(i); continue;
        }
        head = i;
    }
    vi bfs; bfs.pb(head);
    FOR(i, 0, bfs.size()){
        int u = bfs[i];
        for (int v : g[u]){
            d[v] = d[u] + 1;
            bfs.pb(v);
        }
    }
}


int getMinimumFuelCapacity(int x, int y) {
    int l = 0, r = 1000000001;
    while (r-l > 1){
        int u = x; int v = y;
        int m = (l+r)/2;
        while(sub[u] <= m && u != p[u]){
            u = p[u];
        }
        while(sub[v] <= m && v != p[v]){
            v = p[v];
        }
        if (u == v && line[u] <= m && line[u] != -1){
            r = m;
        }else{
            l = m;
        }
    }
    if (r == 1000000001) return -1;
    else return r;
    return -1;
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, vi, vi, vi)':
swap.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   77 |     FOR(i, 0, bfs.size()){
      |         ~~~~~~~~~~~~~~~~               
swap.cpp:77:5: note: in expansion of macro 'FOR'
   77 |     FOR(i, 0, bfs.size()){
      |     ^~~

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