oj.uz

Submission #979644

# Submission time Handle Problem Language Result Execution time Memory
979644 2024-05-11T09:21:04 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 1338 ms 45276 KB 
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>


#include "swap.h"

#include <cassert>
#include <cstdio>


using namespace std;
vector<pair<int, int>> g[200005];
pair<int, int> p[200005];
map<pair<int, int>, int> mp, pos;
set<pair<int, int>> st;
int x, y, mx;
bool ok = 0;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
      x = N;
      y = M;
      if(x - 1 != y) ok = 1;
      for(int i = 0; i < M; i++){
          int a = U[i] + 1, b = V[i] + 1, c = W[i];
          if(a != 1) ok = 1;
          g[a].push_back({b, c});
          g[b].push_back({a, c});
          mp[{a, b}] = c;
          mp[{b, a}] = c;

          pos[{a, b}] = i + 1;
          pos[{b, a}] = i + 1; 

          st.insert({c, i + 1});
      }
}

int getMinimumFuelCapacity(int X, int Y) {

  if(ok){
      X++;
      Y++;
      if(x - 1 == y) return -1;
      else return st.rbegin()->first;
  }
  X++;
  Y++;
  if(x <= 3)
      return -1;
  int mx = 0;
  if(X != 1) mx = mp[{1, X}];
  if(Y != 1) mx = max(mx, mp[{1, Y}]);


  if(X != 1) st.erase({mp[{1, X}], pos[{1, X}]});
  if(Y != 1) st.erase({mp[{1, Y}], pos[{1, Y}]});
  
  pair<int, int> p = *st.begin();
  st.erase(st.begin());
  if(X != 1 && Y != 1){
      st.insert(p);
      if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
      if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
      return max(mx, p.first);
  }
  else{
      pair<int, int> p1 = *st.begin();
      st.insert(p1);
      st.insert(p);
      if(X != 1) st.insert({mp[{1, X}], pos[{1, X}]});
      if(Y != 1) st.insert({mp[{1, Y}], pos[{1, Y}]});
      return max({mx, p.first, p1.first});
  }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 213 ms 34088 KB Output is correct
10 Correct 319 ms 40216 KB Output is correct
11 Correct 306 ms 39756 KB Output is correct
12 Correct 304 ms 41556 KB Output is correct
13 Correct 306 ms 41596 KB Output is correct
14 Correct 218 ms 34128 KB Output is correct
15 Correct 354 ms 42308 KB Output is correct
16 Correct 320 ms 41472 KB Output is correct
17 Correct 412 ms 43424 KB Output is correct
18 Correct 365 ms 43396 KB Output is correct
19 Correct 61 ms 15444 KB Output is correct
20 Correct 362 ms 43608 KB Output is correct
21 Correct 359 ms 42392 KB Output is correct
22 Correct 380 ms 44708 KB Output is correct
23 Correct 345 ms 44940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1089 ms 43512 KB Output is correct
4 Correct 1122 ms 45276 KB Output is correct
5 Correct 1338 ms 44300 KB Output is correct
6 Correct 1209 ms 45108 KB Output is correct
7 Correct 1197 ms 44680 KB Output is correct
8 Correct 1102 ms 43488 KB Output is correct
9 Correct 1126 ms 44404 KB Output is correct
10 Correct 1113 ms 42880 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Incorrect 2 ms 6492 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 6492 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 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 4 ms 6492 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 213 ms 34088 KB Output is correct
10 Correct 319 ms 40216 KB Output is correct
11 Correct 306 ms 39756 KB Output is correct
12 Correct 304 ms 41556 KB Output is correct
13 Correct 306 ms 41596 KB Output is correct
14 Correct 218 ms 34128 KB Output is correct
15 Correct 354 ms 42308 KB Output is correct
16 Correct 320 ms 41472 KB Output is correct
17 Correct 412 ms 43424 KB Output is correct
18 Correct 365 ms 43396 KB Output is correct
19 Correct 1089 ms 43512 KB Output is correct
20 Correct 1122 ms 45276 KB Output is correct
21 Correct 1338 ms 44300 KB Output is correct
22 Correct 1209 ms 45108 KB Output is correct
23 Correct 1197 ms 44680 KB Output is correct
24 Correct 1102 ms 43488 KB Output is correct
25 Correct 1126 ms 44404 KB Output is correct
26 Correct 1113 ms 42880 KB Output is correct
27 Incorrect 3 ms 6748 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 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -