oj.uz

Submission #979746

# Submission time Handle Problem Language Result Execution time Memory
979746 2024-05-11T10:43:19 Z vjudge1 Swapping Cities (APIO20_swap) C++17
30 / 100
 2000 ms 85592 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()) >= 3) 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 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 5 ms 12492 KB Output is correct
9 Correct 219 ms 40572 KB Output is correct
10 Correct 350 ms 47120 KB Output is correct
11 Correct 340 ms 46340 KB Output is correct
12 Correct 374 ms 48516 KB Output is correct
13 Correct 347 ms 48460 KB Output is correct
14 Correct 220 ms 40764 KB Output is correct
15 Correct 395 ms 49048 KB Output is correct
16 Correct 410 ms 48028 KB Output is correct
17 Correct 415 ms 50356 KB Output is correct
18 Correct 435 ms 50340 KB Output is correct
19 Correct 69 ms 21372 KB Output is correct
20 Correct 436 ms 50436 KB Output is correct
21 Correct 318 ms 49148 KB Output is correct
22 Correct 395 ms 51804 KB Output is correct
23 Correct 363 ms 51620 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 1115 ms 50024 KB Output is correct
4 Correct 1236 ms 51748 KB Output is correct
5 Correct 1394 ms 50580 KB Output is correct
6 Correct 1237 ms 51580 KB Output is correct
7 Correct 1399 ms 51124 KB Output is correct
8 Correct 1270 ms 49648 KB Output is correct
9 Correct 1260 ms 50908 KB Output is correct
10 Correct 1287 ms 49300 KB Output is correct

Subtask #3
17.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 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 5 ms 12492 KB Output is correct
9 Correct 4 ms 12120 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 6 ms 12380 KB Output is correct
12 Correct 6 ms 12448 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 5 ms 12452 KB Output is correct
15 Correct 5 ms 12380 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 6 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 5 ms 12380 KB Output is correct
20 Correct 6 ms 12380 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct
22 Correct 8 ms 12632 KB Output is correct
23 Correct 5 ms 12380 KB Output is correct
24 Correct 7 ms 12636 KB Output is correct
25 Correct 7 ms 13144 KB Output is correct
26 Correct 8 ms 12892 KB Output is correct
27 Correct 6 ms 12380 KB Output is correct
28 Correct 7 ms 12892 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 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 5 ms 12492 KB Output is correct
10 Correct 219 ms 40572 KB Output is correct
11 Correct 350 ms 47120 KB Output is correct
12 Correct 340 ms 46340 KB Output is correct
13 Correct 374 ms 48516 KB Output is correct
14 Correct 347 ms 48460 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 6 ms 12448 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 5 ms 12452 KB Output is correct
20 Correct 5 ms 12380 KB Output is correct
21 Correct 6 ms 12380 KB Output is correct
22 Correct 6 ms 12380 KB Output is correct
23 Correct 5 ms 12380 KB Output is correct
24 Correct 5 ms 12380 KB Output is correct
25 Correct 6 ms 12380 KB Output is correct
26 Correct 6 ms 12636 KB Output is correct
27 Correct 8 ms 12632 KB Output is correct
28 Correct 5 ms 12380 KB Output is correct
29 Correct 7 ms 12636 KB Output is correct
30 Correct 7 ms 13144 KB Output is correct
31 Correct 8 ms 12892 KB Output is correct
32 Correct 6 ms 12380 KB Output is correct
33 Correct 7 ms 12892 KB Output is correct
34 Correct 33 ms 17240 KB Output is correct
35 Correct 921 ms 52904 KB Output is correct
36 Correct 889 ms 51728 KB Output is correct
37 Correct 918 ms 50856 KB Output is correct
38 Correct 926 ms 50228 KB Output is correct
39 Correct 861 ms 49656 KB Output is correct
40 Correct 782 ms 46928 KB Output is correct
41 Correct 817 ms 52144 KB Output is correct
42 Correct 982 ms 52340 KB Output is correct
43 Correct 873 ms 53344 KB Output is correct
44 Correct 708 ms 50704 KB Output is correct
45 Correct 1035 ms 65816 KB Output is correct
46 Correct 948 ms 52692 KB Output is correct
47 Correct 963 ms 50600 KB Output is correct
48 Correct 1008 ms 54252 KB Output is correct
49 Correct 677 ms 66900 KB Output is correct
50 Correct 518 ms 54080 KB Output is correct
51 Correct 835 ms 58896 KB Output is correct
52 Correct 1252 ms 72408 KB Output is correct
53 Correct 1265 ms 77440 KB Output is correct
54 Execution timed out 2027 ms 85592 KB Time limit exceeded
55 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 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 5 ms 12492 KB Output is correct
9 Correct 219 ms 40572 KB Output is correct
10 Correct 350 ms 47120 KB Output is correct
11 Correct 340 ms 46340 KB Output is correct
12 Correct 374 ms 48516 KB Output is correct
13 Correct 347 ms 48460 KB Output is correct
14 Correct 220 ms 40764 KB Output is correct
15 Correct 395 ms 49048 KB Output is correct
16 Correct 410 ms 48028 KB Output is correct
17 Correct 415 ms 50356 KB Output is correct
18 Correct 435 ms 50340 KB Output is correct
19 Correct 1115 ms 50024 KB Output is correct
20 Correct 1236 ms 51748 KB Output is correct
21 Correct 1394 ms 50580 KB Output is correct
22 Correct 1237 ms 51580 KB Output is correct
23 Correct 1399 ms 51124 KB Output is correct
24 Correct 1270 ms 49648 KB Output is correct
25 Correct 1260 ms 50908 KB Output is correct
26 Correct 1287 ms 49300 KB Output is correct
27 Correct 6 ms 12380 KB Output is correct
28 Correct 6 ms 12380 KB Output is correct
29 Correct 6 ms 12448 KB Output is correct
30 Correct 5 ms 12380 KB Output is correct
31 Correct 5 ms 12452 KB Output is correct
32 Correct 5 ms 12380 KB Output is correct
33 Correct 6 ms 12380 KB Output is correct
34 Correct 6 ms 12380 KB Output is correct
35 Correct 5 ms 12380 KB Output is correct
36 Correct 33 ms 17240 KB Output is correct
37 Correct 921 ms 52904 KB Output is correct
38 Correct 889 ms 51728 KB Output is correct
39 Correct 918 ms 50856 KB Output is correct
40 Correct 926 ms 50228 KB Output is correct
41 Correct 861 ms 49656 KB Output is correct
42 Correct 782 ms 46928 KB Output is correct
43 Correct 817 ms 52144 KB Output is correct
44 Correct 982 ms 52340 KB Output is correct
45 Correct 873 ms 53344 KB Output is correct
46 Correct 708 ms 50704 KB Output is correct
47 Execution timed out 2070 ms 17164 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 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 5 ms 12492 KB Output is correct
10 Correct 219 ms 40572 KB Output is correct
11 Correct 350 ms 47120 KB Output is correct
12 Correct 340 ms 46340 KB Output is correct
13 Correct 374 ms 48516 KB Output is correct
14 Correct 347 ms 48460 KB Output is correct
15 Correct 220 ms 40764 KB Output is correct
16 Correct 395 ms 49048 KB Output is correct
17 Correct 410 ms 48028 KB Output is correct
18 Correct 415 ms 50356 KB Output is correct
19 Correct 435 ms 50340 KB Output is correct
20 Correct 1115 ms 50024 KB Output is correct
21 Correct 1236 ms 51748 KB Output is correct
22 Correct 1394 ms 50580 KB Output is correct
23 Correct 1237 ms 51580 KB Output is correct
24 Correct 1399 ms 51124 KB Output is correct
25 Correct 1270 ms 49648 KB Output is correct
26 Correct 1260 ms 50908 KB Output is correct
27 Correct 1287 ms 49300 KB Output is correct
28 Correct 6 ms 12380 KB Output is correct
29 Correct 6 ms 12380 KB Output is correct
30 Correct 6 ms 12448 KB Output is correct
31 Correct 5 ms 12380 KB Output is correct
32 Correct 5 ms 12452 KB Output is correct
33 Correct 5 ms 12380 KB Output is correct
34 Correct 6 ms 12380 KB Output is correct
35 Correct 6 ms 12380 KB Output is correct
36 Correct 5 ms 12380 KB Output is correct
37 Correct 33 ms 17240 KB Output is correct
38 Correct 921 ms 52904 KB Output is correct
39 Correct 889 ms 51728 KB Output is correct
40 Correct 918 ms 50856 KB Output is correct
41 Correct 926 ms 50228 KB Output is correct
42 Correct 861 ms 49656 KB Output is correct
43 Correct 782 ms 46928 KB Output is correct
44 Correct 817 ms 52144 KB Output is correct
45 Correct 982 ms 52340 KB Output is correct
46 Correct 873 ms 53344 KB Output is correct
47 Correct 708 ms 50704 KB Output is correct
48 Execution timed out 2070 ms 17164 KB Time limit exceeded
49 Halted 0 ms 0 KB -