oj.uz

Submission #979743

# Submission time Handle Problem Language Result Execution time Memory
979743 2024-05-11T10:42:22 Z vjudge1 Swapping Cities (APIO20_swap) C++14
13 / 100
 1230 ms 51756 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<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, ok1;
vector<int> A, B, C;
bool us[200005];
vector<int> ff[200005];
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;
          mp[{a, b}] = c;
          mp[{b, a}] = c;

          pos[{a, b}] = i + 1;
          pos[{b, a}] = i + 1; 
          ff[a].push_back(b);
          ff[b].push_back(a);
          st.insert({c, i + 1});
          A.push_back(a);
          B.push_back(b);
          C.push_back(c);
      }
      for(int i = 1; i <= x; i++){
        if(ff[i].size() > 2) ok1 = 1;
      }    
} 
int kol = 0, kol1 = 0, kk;
int dist[200005];

void dfs(int k){
  us[k] = 1;
  kol++;
  kol1 += int(g[k].size());
  if(int(g[k].size()) > 0) kk++;
  for(int to : g[k]){
    if(us[to]) continue;
    dfs(to);
  }
}
int getMinimumFuelCapacity(int X, int Y) {
  if(!ok1){
    if(x == y) return st.rbegin()->first;
    else return -1;
  }
  if(ok){
      X++;
      Y++;
      int L = 0, R = 1e9 + 1;
      while(L + 1 < R){
        int mid = (L + R) / 2;
        kol = 0;
        for(int i = 1; i <= x; i++){
          g[i].clear();
          us[i] = 0;
        }
        for(int i = 0; i < y; i++){
            if(C[i] <= mid){
              g[A[i]].push_back(B[i]);
              g[B[i]].push_back(A[i]);
            }
        }
        kol1 = kol = kk = 0;
        dfs(X);
        kol1 /= 2;
        
        if(!us[Y]){
          L = mid;
          continue;
        }
        if(kol - 1 == kol1 && kk == 0){
          L = mid;
          continue;
        }
        R = mid;
        continue;
      }
      if(R == 1000000000) return -1;
      return R;
  }
  else{
    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 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12452 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 221 ms 40608 KB Output is correct
10 Correct 389 ms 47004 KB Output is correct
11 Correct 291 ms 46396 KB Output is correct
12 Correct 334 ms 48476 KB Output is correct
13 Correct 331 ms 48640 KB Output is correct
14 Correct 214 ms 40764 KB Output is correct
15 Correct 354 ms 49228 KB Output is correct
16 Correct 349 ms 48032 KB Output is correct
17 Correct 393 ms 50192 KB Output is correct
18 Correct 355 ms 50344 KB Output is correct
19 Correct 63 ms 21320 KB Output is correct
20 Correct 343 ms 50524 KB Output is correct
21 Correct 327 ms 49336 KB Output is correct
22 Correct 357 ms 51604 KB Output is correct
23 Correct 356 ms 51624 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 1044 ms 49956 KB Output is correct
4 Correct 1107 ms 51756 KB Output is correct
5 Correct 1160 ms 50616 KB Output is correct
6 Correct 1100 ms 51592 KB Output is correct
7 Correct 1090 ms 51196 KB Output is correct
8 Correct 1145 ms 49648 KB Output is correct
9 Correct 1230 ms 50912 KB Output is correct
10 Correct 1154 ms 49416 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12452 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Incorrect 3 ms 12376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12376 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 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 4 ms 12452 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 221 ms 40608 KB Output is correct
10 Correct 389 ms 47004 KB Output is correct
11 Correct 291 ms 46396 KB Output is correct
12 Correct 334 ms 48476 KB Output is correct
13 Correct 331 ms 48640 KB Output is correct
14 Correct 214 ms 40764 KB Output is correct
15 Correct 354 ms 49228 KB Output is correct
16 Correct 349 ms 48032 KB Output is correct
17 Correct 393 ms 50192 KB Output is correct
18 Correct 355 ms 50344 KB Output is correct
19 Correct 1044 ms 49956 KB Output is correct
20 Correct 1107 ms 51756 KB Output is correct
21 Correct 1160 ms 50616 KB Output is correct
22 Correct 1100 ms 51592 KB Output is correct
23 Correct 1090 ms 51196 KB Output is correct
24 Correct 1145 ms 49648 KB Output is correct
25 Correct 1230 ms 50912 KB Output is correct
26 Correct 1154 ms 49416 KB Output is correct
27 Correct 5 ms 12376 KB Output is correct
28 Correct 7 ms 12616 KB Output is correct
29 Correct 6 ms 12380 KB Output is correct
30 Correct 5 ms 12532 KB Output is correct
31 Correct 5 ms 12376 KB Output is correct
32 Incorrect 5 ms 12632 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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