Submission #571184

#	Time	Username	Problem	Language	Result	Execution time	Memory
571184		2fat2code	Swapping Cities (APIO20_swap)	C++17	0 / 100	172 ms	40108 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 300005;

int pardsu[nmax], last, lca[nmax][20], marked[nmax], grad[nmax], val[nmax], timp, in[nmax], out[nmax], apropiat[nmax];
vector<pair<int, pair<int,int>>>edges;
vector<int>nod[nmax];

int findpar(int x){
    if(x != pardsu[x]){
        pardsu[x] = findpar(pardsu[x]);
    }
    return pardsu[x];
}

void dfs(int s, int apr = 0, int par = 0){
    in[s] = ++timp;
    if(marked[s]) apr = s;
    apropiat[s] = apr;
    for(auto it : nod[s]){
        if(it != par){
            dfs(it, apr, s);
        }
    }
    out[s] = ++timp;
}

bool is_lca(int x, int y){
    if(in[x] <= in[y] && out[x] >= out[y]) return true;
    else return false;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    last = N;
    for(int i=1;i<=N;i++) pardsu[i] = i;
    for(int i=0;i<M;i++){
        U[i]++; V[i]++;
        edges.push_back({W[i], {U[i], V[i]}});
    }
    sort(all(edges));
    for(auto it : edges){
        int x = findpar(it.sc.fr);
        int y = findpar(it.sc.sc);
        ++last;
        pardsu[y] = last;
        pardsu[x] = last;
        pardsu[last] = last;
        val[last] = it.fr;
        grad[it.sc.sc]++;
        grad[it.sc.fr]++;
        lca[x][0] = last;
        lca[y][0] = last;
        nod[last].push_back(x);
        if(x != y) nod[last].push_back(y);
        if(x == y){
            marked[last] = 1;
        }
        else{
            if(grad[it.sc.sc] >= 3 || grad[it.sc.fr] >= 3){
                marked[last] = 1;
            }
        }
    }
    for(int i=1;i<=19;i++){
        for(int j=1;j<=last;j++){
            lca[j][i] = lca[lca[j][i-1]][i-1];
        }
    }
    dfs(last);
   // assert(last == N + M);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int curr;
    if(is_lca(X, Y)) curr = X;
    else if(is_lca(Y, X)) curr = Y;
    else{
        for(int i=19;i>=0;i--){
            if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
        }
        curr = lca[curr][0];
    }
    if(!apropiat[curr]) return -1;
    else{
        return val[apropiat[curr]];
    }
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:86:27: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |             if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
      |                ~~~~~~~~~~~^

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