Submission #403736

#	Time	Username	Problem	Language	Result	Execution time	Memory
403736		aryan12	Swapping Cities (APIO20_swap)	C++17	37 / 100	2072 ms	13636 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

struct UFDS {
  int parent;
  bool line;
  pair<int, int> endpoints;
} Data[N];

vector<pair<pair<int, int>, int> > edge;

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
  return a.second < b.second;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  for(int i = 0; i < N; i++) {
    Data[i].parent = i;
    Data[i].line = true;
    Data[i].endpoints = {i, i};
  }
  for(int i = 0; i < M; i++) {
     edge.push_back(make_pair(make_pair(U[i], V[i]), W[i]));
  }
  sort(edge.begin(), edge.end(), cmp);
}

int Find(int x) {
  if(Data[x].parent == x)
    return x;
  return Data[x].parent = Find(Data[x].parent);
}

void Unite(int a, int b) {
  int parA = Find(a), parB = Find(b);
  if(parA == parB) {
    Data[parA].line = false;
    Data[parA].endpoints = {-1, -1};
  }
  else {
    Data[parB].parent = parA;
    if(!Data[parB].line || !Data[parA].line) {
      Data[parA].line = false;
      Data[parA].endpoints = {-1, -1};
    }
    else {
      if(Data[parA].endpoints.first != a) {
        swap(Data[parA].endpoints.first, Data[parA].endpoints.second);
      }
      if(Data[parB].endpoints.first != b) {
        swap(Data[parB].endpoints.first, Data[parB].endpoints.second);
      }
      if(a != Data[parA].endpoints.first || b != Data[parB].endpoints.first) {
        Data[parA].line = false;
        Data[parA].endpoints = {-1, -1};
      }
      else {
        Data[parA].endpoints.first = Data[parB].endpoints.second;
      }
    }
  }
}

void Ini() {
  for(int i = 0; i < N; i++) {
    Data[i].parent = i;
    Data[i].line = true;
    Data[i].endpoints = {i, i};
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  Ini();
  //cout << "X = " << X << ", Y = " << Y << "\n";
  for(int i = 0; i < edge.size(); i++) {
    if(Find(edge[i].first.first) != Find(edge[i].first.second)) {
      //cout << "Uniting because of diff components: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
      Unite(edge[i].first.first, edge[i].first.second);
    }
    else if(Data[edge[i].first.first].line) {
      //cout << "Uniting because its a line: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
      Unite(edge[i].first.first, edge[i].first.second);
    }
    //else {
      //cout << "Not uniting: " << edge[i].first.first << ", " << edge[i].first.second << "\n";
    //}
    //cout << "Components: " << Find(X) << " " << Find(Y) << "\n";
    //cout << "Is it a line? : " << Data[X].line << "\n";
    if(Find(X) == Find(Y) && !Data[Find(X)].line) {
      return edge[i].second;
    }
  }
  return -1;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i = 0; i < edge.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

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