oj.uz

Submission #979621

# Submission time Handle Problem Language Result Execution time Memory
979621 2024-05-11T09:01:13 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 428 ms 43448 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>

#include <string>

#include <vector>
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 N, M;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
      for(int i = 0; i < M; i++){
          int a = U[i] + 1, b = V[i] + 1, c = W[i] + 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) {
  X++;
    Y++;
    if(N <= 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 3 ms 6836 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 247 ms 34132 KB Output is correct
10 Correct 293 ms 40300 KB Output is correct
11 Correct 265 ms 39764 KB Output is correct
12 Correct 321 ms 41772 KB Output is correct
13 Correct 293 ms 41556 KB Output is correct
14 Correct 219 ms 34128 KB Output is correct
15 Correct 372 ms 42280 KB Output is correct
16 Correct 359 ms 41288 KB Output is correct
17 Correct 345 ms 43448 KB Output is correct
18 Correct 428 ms 43436 KB Output is correct
19 Incorrect 56 ms 14192 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Incorrect 287 ms 42320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 3 ms 6836 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Incorrect 2 ms 6488 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 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 3 ms 6836 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 247 ms 34132 KB Output is correct
10 Correct 293 ms 40300 KB Output is correct
11 Correct 265 ms 39764 KB Output is correct
12 Correct 321 ms 41772 KB Output is correct
13 Correct 293 ms 41556 KB Output is correct
14 Correct 219 ms 34128 KB Output is correct
15 Correct 372 ms 42280 KB Output is correct
16 Correct 359 ms 41288 KB Output is correct
17 Correct 345 ms 43448 KB Output is correct
18 Correct 428 ms 43436 KB Output is correct
19 Incorrect 287 ms 42320 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 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -