Submission #743676

#	Time	Username	Problem	Language	Result	Execution time	Memory
743676		speedyArda	Swapping Cities (APIO20_swap)	C++14	13 / 100	146 ms	15424 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
vector < vector< pair<ll, ll> > > adj(MAXN);
int sum_dist = 0;
ll dist[MAXN];

int edges, max_ed = 0, u_max;
int n, m;

/*void dfs(int v, int p, ll val = 1e9)
{

    for(int i = 0; i < adj[v]).size(); i++)
    {
      pair<ll, ll> e = adj[v][i];
      if(e.second == p)
        continue;
      if(e == adj[v][0]) {
        if(adj[v].size() > 1 && adj[v][1].second != p)
          val = min(val, adj[v][1].first);
        else if(adj[v].size() > 2)
          val = min(val, adj[v][2].first);
      }
      else {
        if(adj[v][0].second != p)
          val = min(val, adj[v][0].first);
        else if(adj[v].size() > 1)
          val = min(val, adj[v][1].first);
      }
      dist[e.second] = dist[v] + e.first;
      dfs(e, v, val);

    }

    dist[v] += val;


}*/ 
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {

    m = M;
    n = N;

    for(int i = 0; i < M; i++)
    {
      adj[U[i]].push_back({W[i], V[i]});
      adj[V[i]].push_back({W[i], V[i]});
      dist[V[i]] = W[i]; // for sub 2
      u_max = max(u_max, U[i]);
      sum_dist = max(sum_dist, W[i]);
    }
    for(int i = 0; i < N; i++)
    {
      sort(adj[i].begin(), adj[i].end());
      max_ed = max(max_ed, (int)adj[i].size());
    }

}

int getMinimumFuelCapacity(int X, int Y) {
  if(max_ed <= 2) // Sub 1
  {
    if(m == n - 1)
      return -1;
    else
      return sum_dist;
  }

  if(u_max == 0) // Sub 2
  {
    if(X > Y)
      swap(X, Y);
    ll sum = max(dist[X], dist[Y]);
    if(X != 0) {
      
      sum = max(sum, (adj[0][0].second != X && adj[0][0].second != Y) ? adj[0][0].first : ((adj[0][1].second != X && adj[0][1].second != Y) ? adj[0][1].first : adj[0][2].first));
    } else 
    {
      sum = max(sum, (adj[0][0].second != Y ? max(adj[0][0].first, adj[0][1].second != Y ? adj[0][1].first : adj[0][2].first) : max(adj[0][1].first, adj[0][2].first)));
    }
    return sum;
  }


  return 0;
}

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