Submission #385173

#	Time	Username	Problem	Language	Result	Execution time	Memory
385173		kwongweng	Swapping Cities (APIO20_swap)	C++17	6 / 100	118 ms	13944 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

int l = 0;
vector<pair<int, ii>> edges;
vi p, r, deg, maxi, num, sz;
void init(int n, int m, vi U, vi V, vi W) {
    FOR(i, 0, m){
        edges.pb({W[i], {U[i], V[i]}});
        l = max(l, W[i]);
    }
    if (m == n-1) l = -1;
    sort(edges.begin(), edges.end());
    p.resize(n);
    r.resize(n);
    deg.resize(n);
    maxi.resize(n);
    num.resize(n);
    sz.resize(n);
}

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

void Union(int c, int d){
    int a = get(c), b = get(d);
    if (a == b) return;
    if (r[a] == r[b]) r[a]++;
    if (r[a] > r[b]){
        p[b] = a;
        maxi[a] = max(maxi[b], maxi[a]);
        num[a] += num[b];
        sz[a] += sz[b];
    }else{
        p[a] = b;
        maxi[b] = max(maxi[a], maxi[b]);
        num[b] += num[a];
        sz[b] += sz[a];
    }
}


int getMinimumFuelCapacity(int x, int y) {
    return l;
    FOR(i, 0, p.size()) p[i] = i;
    FOR(i, 0, r.size()){
        r[i] = 0; deg[i] = 0, maxi[i] = 0; num[i] = 0; sz[i] = 1;
    }
    FOR(i, 0, edges.size()){
        int a = edges[i].S.F, b = edges[i].S.S;
        Union(a, b);
        deg[a]++; deg[b]++;
        maxi[get(a)] = max(maxi[get(a)], deg[a]);
        maxi[get(b)] = max(maxi[get(b)], deg[b]);
        num[get(a)]++;
        if (get(x) != get(y)) continue;
        if (maxi[get(x)] < 3 && num[get(x)] < sz[get(x)]) continue;
        return edges[i].F;
    }
    return -1;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
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++)
......
   57 |     FOR(i, 0, p.size()) p[i] = i;
      |         ~~~~~~~~~~~~~~                 
swap.cpp:57:5: note: in expansion of macro 'FOR'
   57 |     FOR(i, 0, p.size()) p[i] = i;
      |     ^~~
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++)
......
   58 |     FOR(i, 0, r.size()){
      |         ~~~~~~~~~~~~~~                 
swap.cpp:58:5: note: in expansion of macro 'FOR'
   58 |     FOR(i, 0, r.size()){
      |     ^~~
swap.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   61 |     FOR(i, 0, edges.size()){
      |         ~~~~~~~~~~~~~~~~~~             
swap.cpp:61:5: note: in expansion of macro 'FOR'
   61 |     FOR(i, 0, edges.size()){
      |     ^~~

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