oj.uz

Submission #979742

# Submission time Handle Problem Language Result Execution time Memory
979742 2024-05-11T10:41:54 Z vjudge1 Swapping Cities (APIO20_swap) C++17
13 / 100
 1270 ms 51748 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 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 4 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 214 ms 40660 KB Output is correct
10 Correct 325 ms 46948 KB Output is correct
11 Correct 339 ms 46352 KB Output is correct
12 Correct 323 ms 48444 KB Output is correct
13 Correct 343 ms 48536 KB Output is correct
14 Correct 253 ms 40708 KB Output is correct
15 Correct 398 ms 49196 KB Output is correct
16 Correct 387 ms 48032 KB Output is correct
17 Correct 349 ms 50380 KB Output is correct
18 Correct 368 ms 50212 KB Output is correct
19 Correct 63 ms 21332 KB Output is correct
20 Correct 350 ms 50512 KB Output is correct
21 Correct 328 ms 49148 KB Output is correct
22 Correct 354 ms 51740 KB Output is correct
23 Correct 362 ms 51624 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 1091 ms 50156 KB Output is correct
4 Correct 1208 ms 51748 KB Output is correct
5 Correct 1133 ms 50584 KB Output is correct
6 Correct 1192 ms 51580 KB Output is correct
7 Correct 1112 ms 51124 KB Output is correct
8 Correct 1194 ms 49560 KB Output is correct
9 Correct 1145 ms 50912 KB Output is correct
10 Correct 1270 ms 49300 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12120 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 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 4 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 214 ms 40660 KB Output is correct
10 Correct 325 ms 46948 KB Output is correct
11 Correct 339 ms 46352 KB Output is correct
12 Correct 323 ms 48444 KB Output is correct
13 Correct 343 ms 48536 KB Output is correct
14 Correct 253 ms 40708 KB Output is correct
15 Correct 398 ms 49196 KB Output is correct
16 Correct 387 ms 48032 KB Output is correct
17 Correct 349 ms 50380 KB Output is correct
18 Correct 368 ms 50212 KB Output is correct
19 Correct 1091 ms 50156 KB Output is correct
20 Correct 1208 ms 51748 KB Output is correct
21 Correct 1133 ms 50584 KB Output is correct
22 Correct 1192 ms 51580 KB Output is correct
23 Correct 1112 ms 51124 KB Output is correct
24 Correct 1194 ms 49560 KB Output is correct
25 Correct 1145 ms 50912 KB Output is correct
26 Correct 1270 ms 49300 KB Output is correct
27 Correct 5 ms 12380 KB Output is correct
28 Correct 6 ms 12380 KB Output is correct
29 Correct 6 ms 12380 KB Output is correct
30 Correct 8 ms 12296 KB Output is correct
31 Correct 5 ms 12376 KB Output is correct
32 Incorrect 5 ms 12380 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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