Submission #1233467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233467		dssfsuper2	Swapping Cities (APIO20_swap)	C++20	0 / 100	2092 ms	19180 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;



vector<vector<pii>> adj;
multiset<pii> stac;
vector<pii> lowest;
int n,m;
int total=0;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
  n=N;
  m=M;
  adj.resize(N+1);
  vector<int> deg(N+1);
  for(int i = 0;i<M;i++){
    deg[U[i]]++;
    deg[V[i]]++;
    
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }
  if(*max_element(deg.begin(), deg.end())>=3)total=1;
  if(*min_element(deg.begin(), deg.end())==2 && *(max_element(deg.begin(), deg.end()))==2)total=1;
}

int dijkstra(int X, int Y){
  stac.clear();
  stac.insert({0, X});
  lowest.assign(n+1, {1e9+1, 1e9+1});
  lowest[X]={0, 1e9+1};
  while(!stac.empty()){
    auto node = *(stac.begin());
    stac.erase(stac.begin());
    if(lowest[node.second].second!=1e9+1 )continue;
    if(node.first>=lowest[node.second].first)lowest[node.second].second=node.first;
    else lowest[node.second].first=node.first;
    for(auto thing:adj[node.second]){
      if(lowest[thing.first].second<=max(thing.second, node.first))continue;
      stac.insert({max(node.first, thing.second), thing.first});
    }

  }
  return lowest[Y].second;
}
int getMinimumFuelCapacity(int X, int Y) {
  if(!total)return -1;
  return dijkstra(X, Y);
  
}

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