Submission #712387

#	Time	Username	Problem	Language	Result	Execution time	Memory
712387		Ronin13	Swapping Cities (APIO20_swap)	C++14	23 / 100	2073 ms	94528 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#include <vector>

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

*/
using namespace std;


const int nmax = 1000000;

vector <vector <pii> > g(nmax);

vector <vector <int> > cmp(nmax);

vector <pii> par[nmax];



int val[nmax];
int l[nmax], r[nmax];
void make_set(int v){
    par[v].pb({v, 0});
    cmp[v].pb(v);
    val[v] = 1e9 + 1;
    l[v] = r[v] = v;
}

void union_sets(int a, int b, int len){
    if(par[a].back().f == par[b].back().f){
        if(val[a] == 1e9 +1){
            int x = par[a].back().f;
            for(int to : cmp[x]){
                val[to] = len;
            }
        }
        return;
    }
    int x = par[a].back().f, y = par[b].back().f;
    if(cmp[x].size() < cmp[y].size())
        swap(x, y), swap(a, b);
    for(int to : cmp[y])
        cmp[x].pb(to), par[to].pb({x, len});
    if(val[x] == 1e9 + 1 || val[y] == 1e9 + 1){
        int mn = min(val[x], val[y]);
        if(mn != 1e9 + 1){
        for(int to : cmp[x])
            val[to] = min(val[to], len);
        return;}
    }

    if(l[x] == a && l[y] == b){
        l[x] = r[y];
        return;
    }
    if(l[x] == a && r[y] == b){
        l[x] = l[y];
        return;
    }
    if(r[x] == a && l[y] == b){
        r[x] = r[y];
        return;
    }
    if(r[x] == a && r[y] == b){
        r[x] = l[y];
        return;
    }
    for(int to : cmp[x])
        val[to] =    min(val[to], len);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    int n = N;
    vector <pair <int, pii> > ed;
    for(int i = 0; i < n; i++)
        make_set(i);
    for(int i = 0; i < M; i++){
        ed.pb({W[i], {U[i], V[i]}});
    }
    sort(ed.begin(), ed.end());
    for(int i = 0; i < ed.size(); i++){
        union_sets(ed[i].s.f, ed[i].s.s, ed[i].f);
        //cout << 1;
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if(val[X] == 1e9 + 1)
        return -1;
    int x = X, y = Y;
    int sz = par[x].size() - 1;
    int sz2 = par[y].size() - 1;
    int ans = 1e9 + 1;
    while(sz >= 0 && sz2 >= 0){

        if(par[x][sz].f== par[y][sz2].f)
            ans = min(ans, max(par[x][sz].s, par[y][sz2].s));
        sz--;
        sz2--;
    }
  int u = max(min(val[X],val[y]), ans);
  if(u == 1e9 + 1)
    u = -1;
  return u;
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:102:22: 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]
  102 |     for(int i = 0; i < ed.size(); i++){
      |                    ~~^~~~~~~~~~~

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