Submission #743679

#	Time	Username	Problem	Language	Result	Execution time	Memory
743679		speedyArda	Swapping Cities (APIO20_swap)	C++14	6 / 100	92 ms	16352 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;
int dist[MAXN];
int edge_cnt[MAXN], par[MAXN], sz[MAXN], edge_sz[MAXN], max_sz[MAXN], cnt[MAXN];
int max_ed = 0, u_max;
int n, m;
vector < pair<int, pair<int, int> > > edges;

int find(int v)
{
  if(par[v] == v)
    return v;
  return par[v] = find(par[v]);
}

void merge(int a, int b)
{
  int maxi = max(cnt[a], cnt[b]);
  a = find(a), b = find(b);
  if(a == b) {
    edge_sz[a]++;
    max_sz[a] = max(max_sz[a], maxi);
    return;
  }
  if(sz[a] < sz[b])
    swap(a, b);
  par[b] = a;
  sz[a] += sz[b];
  edge_sz[a]++;
  max_sz[a] = max(max_sz[a], maxi);
}
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++)
    {
      edge_cnt[U[i]]++;
      edge_cnt[V[i]]++;
      dist[V[i]] = W[i]; // for sub 2
      edges.push_back({W[i], {U[i], V[i]}});
      u_max = max(u_max, U[i]);
      sum_dist = max(sum_dist, W[i]);
    }
    sort(edges.begin(), edges.end());
    for(int i = 0; i < N; i++)
    {
      max_ed = max(max_ed, (int)edge_cnt[i]);
    }

}

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;
  }

  for(int i = 0; i < n; i++)
  {
    cnt[i] = 0;
    edge_sz[i] = max_sz[i] = 0;
    sz[i] = 1;
    par[i] = i;
  }

  for(pair<int, pair<int, int> > edge : edges)
  {
    cnt[edge.second.first]++;
    cnt[edge.second.second]++;
    merge(edge.second.first, edge.second.second);

    if(find(edge.second.first) == find(edge.second.second))
    {
      int curr = find(edge.second.first);
      if(edge_sz[curr] >= sz[curr] || max_sz[curr] > 2)
        return edge.first;
    }
  }


  return -1;


  return 0;
}

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