oj.uz

Submission #743676

# Submission time Handle Problem Language Result Execution time Memory
743676 2023-05-17T16:58:21 Z speedyArda Swapping Cities (APIO20_swap) C++14
13 / 100
 146 ms 15424 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;
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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 44 ms 9548 KB Output is correct
10 Correct 57 ms 11064 KB Output is correct
11 Correct 57 ms 11032 KB Output is correct
12 Correct 61 ms 11364 KB Output is correct
13 Correct 72 ms 11328 KB Output is correct
14 Correct 47 ms 9660 KB Output is correct
15 Correct 146 ms 13076 KB Output is correct
16 Correct 100 ms 12796 KB Output is correct
17 Correct 106 ms 13304 KB Output is correct
18 Correct 134 ms 13232 KB Output is correct
19 Correct 56 ms 7732 KB Output is correct
20 Correct 106 ms 14920 KB Output is correct
21 Correct 108 ms 14928 KB Output is correct
22 Correct 113 ms 15416 KB Output is correct
23 Correct 129 ms 15424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 98 ms 13536 KB Output is correct
4 Correct 100 ms 14516 KB Output is correct
5 Correct 106 ms 14724 KB Output is correct
6 Correct 96 ms 14484 KB Output is correct
7 Correct 106 ms 14672 KB Output is correct
8 Correct 108 ms 14376 KB Output is correct
9 Correct 121 ms 14492 KB Output is correct
10 Correct 101 ms 14296 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2688 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 2672 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 44 ms 9548 KB Output is correct
10 Correct 57 ms 11064 KB Output is correct
11 Correct 57 ms 11032 KB Output is correct
12 Correct 61 ms 11364 KB Output is correct
13 Correct 72 ms 11328 KB Output is correct
14 Correct 47 ms 9660 KB Output is correct
15 Correct 146 ms 13076 KB Output is correct
16 Correct 100 ms 12796 KB Output is correct
17 Correct 106 ms 13304 KB Output is correct
18 Correct 134 ms 13232 KB Output is correct
19 Correct 98 ms 13536 KB Output is correct
20 Correct 100 ms 14516 KB Output is correct
21 Correct 106 ms 14724 KB Output is correct
22 Correct 96 ms 14484 KB Output is correct
23 Correct 106 ms 14672 KB Output is correct
24 Correct 108 ms 14376 KB Output is correct
25 Correct 121 ms 14492 KB Output is correct
26 Correct 101 ms 14296 KB Output is correct
27 Incorrect 3 ms 2644 KB Output isn't correct
28 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 -