oj.uz

Submission #743679

# Submission time Handle Problem Language Result Execution time Memory
743679 2023-05-17T17:12:17 Z speedyArda Swapping Cities (APIO20_swap) C++14
6 / 100
 92 ms 16352 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2672 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2680 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Correct 32 ms 7180 KB Output is correct
10 Correct 39 ms 7712 KB Output is correct
11 Correct 40 ms 7692 KB Output is correct
12 Correct 42 ms 7816 KB Output is correct
13 Correct 41 ms 7780 KB Output is correct
14 Correct 37 ms 7256 KB Output is correct
15 Correct 92 ms 9556 KB Output is correct
16 Correct 91 ms 9540 KB Output is correct
17 Correct 88 ms 9588 KB Output is correct
18 Correct 89 ms 9568 KB Output is correct
19 Correct 48 ms 7316 KB Output is correct
20 Correct 86 ms 10064 KB Output is correct
21 Correct 86 ms 10412 KB Output is correct
22 Correct 89 ms 10708 KB Output is correct
23 Correct 92 ms 10660 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Runtime error 74 ms 16352 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2672 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2680 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Incorrect 2 ms 2644 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2672 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2680 KB Output is correct
8 Correct 2 ms 2676 KB Output is correct
9 Correct 32 ms 7180 KB Output is correct
10 Correct 39 ms 7712 KB Output is correct
11 Correct 40 ms 7692 KB Output is correct
12 Correct 42 ms 7816 KB Output is correct
13 Correct 41 ms 7780 KB Output is correct
14 Correct 37 ms 7256 KB Output is correct
15 Correct 92 ms 9556 KB Output is correct
16 Correct 91 ms 9540 KB Output is correct
17 Correct 88 ms 9588 KB Output is correct
18 Correct 89 ms 9568 KB Output is correct
19 Runtime error 74 ms 16352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -