Submission #735480

#	Time	Username	Problem	Language	Result	Execution time	Memory
735480		keisuke6	Swapping Cities (APIO20_swap)	C++14	0 / 100	1 ms	468 KiB

swap

#include "swap.h"
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <cassert>
using namespace std;
int N,M;
vector<int> U,V,W,W_;
vector<tuple<int,int,int>> S = {};
struct Unionfind{
  vector<int> par, siz;
  //初期化
  Unionfind(int n) : par(n,-1) , siz(n,1) {}
  int root(int x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
  bool issame(int x,int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if(x ==  y) return false;
    if(siz[x] < siz[y]) swap(x,y);
    par[y] =  x;
    siz[x] += siz[y];
    return  true;
  }
  int size(int x) {
    return siz[root(x)];
  }
};
void init(int NN, int MM,
          std::vector<int> UU, std::vector<int> VV, std::vector<int> WW) {
            N = NN;
            M = MM;
            U = UU;
            V = VV;
            W = WW;
            W_ = W;
            for(int i=0;i<M;i++){
              S.push_back({W[i],U[i],V[i]});
            }
            sort(S.begin(),S.end());
}
 
int getMinimumFuelCapacity(int X, int Y) {
  vector<int> E = {};
  vector<vector<int>> G(N);
  bool cone = false;
  Unionfind uf(N);
  for(int i=0;i<M;i++){
    int w,u,v;
    tie(w,u,v) = S[i];
    if(cone && uf.issame(u,v) && uf.issame(u,X)) return w;
    uf.unite(u,v);
    G[u].push_back(v);
    G[v].push_back(u);
    if(uf.issame(X,Y) && !cone){
      cone = true;
      vector<int> dist(N,1e9);
      dist[X] = 0;
      queue<int> q;
      q.push(X);
      while(!q.empty()){
        int pos = q.front();
        q.pop();
        for(int x:G[pos]){
          if(dist[x] != 1e9) continue;
          dist[x] = dist[pos] + 1;
          q.push(x);
          continue;
        }
      }
      int now = Y;
      while(now){
        if(now != Y) E.push_back(now);
        for(int x:G[now]){
          if(dist[x]+1 == dist[now]){
            now = x;
            continue;
          }
        }
      }
      for(int x:E){
        if(G[x].size() >= 3) return w;
      }
    }
    if(cone){
      if(G[u].size() >= 3 || G[v].size() >= 3) return w;
    }
    assert(false);
  }
  return -1;
}

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