oj.uz

Submission #743674

# Submission time Handle Problem Language Result Execution time Memory
743674 2023-05-17T16:45:52 Z speedyArda Swapping Cities (APIO20_swap) C++14
0 / 100
 137 ms 14800 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);
ll 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 += 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 = 0;
    if(X != 0) {
      sum = 2LL * (dist[X] + dist[Y]) + 2LL * ((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].size() > 2) ? adj[0][2].first : 0LL));
    } else 
    {
      sum = 2LL * (dist[Y]  + (adj[0][0].second != Y ? adj[0][0].first + (adj[0][1].second != Y ? adj[0][1].first : adj[0][2].first): adj[0][1].first + adj[0][2].first));
    }
    return sum;
  }


  return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 45 ms 10156 KB Output is correct
10 Correct 66 ms 11704 KB Output is correct
11 Correct 54 ms 11556 KB Output is correct
12 Correct 59 ms 11944 KB Output is correct
13 Correct 60 ms 11944 KB Output is correct
14 Correct 52 ms 10368 KB Output is correct
15 Correct 119 ms 14272 KB Output is correct
16 Correct 137 ms 14084 KB Output is correct
17 Correct 123 ms 14444 KB Output is correct
18 Correct 130 ms 14540 KB Output is correct
19 Incorrect 60 ms 8572 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Incorrect 123 ms 14800 KB Output isn't correct
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 2672 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2772 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 2672 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 45 ms 10156 KB Output is correct
10 Correct 66 ms 11704 KB Output is correct
11 Correct 54 ms 11556 KB Output is correct
12 Correct 59 ms 11944 KB Output is correct
13 Correct 60 ms 11944 KB Output is correct
14 Correct 52 ms 10368 KB Output is correct
15 Correct 119 ms 14272 KB Output is correct
16 Correct 137 ms 14084 KB Output is correct
17 Correct 123 ms 14444 KB Output is correct
18 Correct 130 ms 14540 KB Output is correct
19 Incorrect 123 ms 14800 KB Output isn't correct
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 -