oj.uz

Submission #532867

# Submission time Handle Problem Language Result Execution time Memory
532867 2022-03-04T06:22:48 Z ohohorz Swapping Cities (APIO20_swap) C++14
7 / 100
 791 ms 32724 KB 
#include "swap.h"

#include <vector>
#include<set>
#include<algorithm>
#include<climits>
#include<map>
using namespace std;

// #define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define sz(x) (int)x.size()

const int MAXN = 1e5 + 5;
const int INF = INT_MAX;
const int LOGN = 22;

int n, m;
vector< pair <int,int> > g[MAXN];
multiset<int> wt;
map<pii,int> who;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N,m = M;
  for(int i = 0;i < m;i++){
    int u = U[i] + 1;
    int v = V[i] + 1;
    g[u].pb(mp(v, W[i]));
    wt.insert(W[i]);
    g[v].pb(mp(u, W[i]));
    who[mp(u, v)] = W[i];
    who[mp(v, u)] = W[i];
  }
  
}

int getMinimumFuelCapacity(int X, int Y) {
  X++, Y++;
  if(sz(g[1]) < 3) return -1;
  if(X==1){
    int w = who[mp(X, Y)];
    int ans = w;
    wt.erase(wt.find(w));
    int w2 = *(wt.begin());
    ans = max(ans, w2);
    wt.erase(wt.find(w2));
    
    int w3 = *(wt.begin());
    ans = max(ans, w3);
    wt.insert(w);
    wt.insert(w2);
    return ans;
  }
  int w = who[mp(X, 1)];
  int ans = w;
  int w2 = who[mp(Y, 1)];
  ans = max(ans, w2);
  wt.erase(wt.find(w));
  wt.erase(wt.find(w2));
  ans = max(ans, *(wt.begin()));
  wt.insert(w);
  wt.insert(w2);
  return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 2 ms 2508 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 187 ms 20420 KB Output is correct
10 Correct 244 ms 24364 KB Output is correct
11 Correct 235 ms 24004 KB Output is correct
12 Correct 259 ms 25212 KB Output is correct
13 Correct 263 ms 25260 KB Output is correct
14 Correct 188 ms 20488 KB Output is correct
15 Correct 298 ms 26344 KB Output is correct
16 Correct 307 ms 25808 KB Output is correct
17 Correct 321 ms 27060 KB Output is correct
18 Correct 327 ms 27052 KB Output is correct
19 Incorrect 64 ms 8508 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 751 ms 27768 KB Output is correct
4 Correct 791 ms 32724 KB Output is correct
5 Correct 789 ms 32304 KB Output is correct
6 Correct 750 ms 32684 KB Output is correct
7 Correct 774 ms 32616 KB Output is correct
8 Correct 729 ms 31632 KB Output is correct
9 Correct 756 ms 32312 KB Output is correct
10 Correct 729 ms 31476 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2508 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 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 2 ms 2508 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 187 ms 20420 KB Output is correct
10 Correct 244 ms 24364 KB Output is correct
11 Correct 235 ms 24004 KB Output is correct
12 Correct 259 ms 25212 KB Output is correct
13 Correct 263 ms 25260 KB Output is correct
14 Correct 188 ms 20488 KB Output is correct
15 Correct 298 ms 26344 KB Output is correct
16 Correct 307 ms 25808 KB Output is correct
17 Correct 321 ms 27060 KB Output is correct
18 Correct 327 ms 27052 KB Output is correct
19 Correct 751 ms 27768 KB Output is correct
20 Correct 791 ms 32724 KB Output is correct
21 Correct 789 ms 32304 KB Output is correct
22 Correct 750 ms 32684 KB Output is correct
23 Correct 774 ms 32616 KB Output is correct
24 Correct 729 ms 31632 KB Output is correct
25 Correct 756 ms 32312 KB Output is correct
26 Correct 729 ms 31476 KB Output is correct
27 Incorrect 3 ms 2756 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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