oj.uz

Submission #979745

# Submission time Handle Problem Language Result Execution time Memory
979745 2024-05-11T10:42:53 Z vjudge1 Swapping Cities (APIO20_swap) C++14
30 / 100
 2000 ms 85448 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 12124 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 12376 KB Output is correct
6 Correct 4 ms 12380 KB Output is correct
7 Correct 4 ms 12376 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 215 ms 40700 KB Output is correct
10 Correct 317 ms 47220 KB Output is correct
11 Correct 290 ms 46336 KB Output is correct
12 Correct 338 ms 48572 KB Output is correct
13 Correct 302 ms 48396 KB Output is correct
14 Correct 217 ms 40764 KB Output is correct
15 Correct 352 ms 49144 KB Output is correct
16 Correct 333 ms 48204 KB Output is correct
17 Correct 355 ms 50228 KB Output is correct
18 Correct 354 ms 50340 KB Output is correct
19 Correct 67 ms 21332 KB Output is correct
20 Correct 334 ms 50500 KB Output is correct
21 Correct 341 ms 49140 KB Output is correct
22 Correct 351 ms 51640 KB Output is correct
23 Correct 352 ms 51632 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 3 ms 12124 KB Output is correct
3 Correct 1072 ms 50412 KB Output is correct
4 Correct 1116 ms 51732 KB Output is correct
5 Correct 1182 ms 50700 KB Output is correct
6 Correct 1056 ms 51580 KB Output is correct
7 Correct 1139 ms 51472 KB Output is correct
8 Correct 1125 ms 49928 KB Output is correct
9 Correct 1073 ms 51048 KB Output is correct
10 Correct 1088 ms 49424 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 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 12376 KB Output is correct
6 Correct 4 ms 12380 KB Output is correct
7 Correct 4 ms 12376 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 5 ms 12388 KB Output is correct
11 Correct 6 ms 12380 KB Output is correct
12 Correct 6 ms 12380 KB Output is correct
13 Correct 5 ms 12380 KB Output is correct
14 Correct 5 ms 12380 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 6 ms 12468 KB Output is correct
17 Correct 6 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 6 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 6 ms 12636 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 12892 KB Output is correct
26 Correct 8 ms 12944 KB Output is correct
27 Correct 6 ms 12624 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 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 3 ms 12124 KB Output is correct
6 Correct 4 ms 12376 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12376 KB Output is correct
9 Correct 4 ms 12380 KB Output is correct
10 Correct 215 ms 40700 KB Output is correct
11 Correct 317 ms 47220 KB Output is correct
12 Correct 290 ms 46336 KB Output is correct
13 Correct 338 ms 48572 KB Output is correct
14 Correct 302 ms 48396 KB Output is correct
15 Correct 5 ms 12388 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 12468 KB Output is correct
22 Correct 6 ms 12380 KB Output is correct
23 Correct 5 ms 12380 KB Output is correct
24 Correct 6 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 6 ms 12636 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 12892 KB Output is correct
31 Correct 8 ms 12944 KB Output is correct
32 Correct 6 ms 12624 KB Output is correct
33 Correct 7 ms 12892 KB Output is correct
34 Correct 38 ms 17500 KB Output is correct
35 Correct 939 ms 53156 KB Output is correct
36 Correct 885 ms 51876 KB Output is correct
37 Correct 881 ms 51104 KB Output is correct
38 Correct 952 ms 50196 KB Output is correct
39 Correct 848 ms 49888 KB Output is correct
40 Correct 798 ms 46496 KB Output is correct
41 Correct 877 ms 52180 KB Output is correct
42 Correct 1051 ms 52604 KB Output is correct
43 Correct 965 ms 53184 KB Output is correct
44 Correct 699 ms 50836 KB Output is correct
45 Correct 1115 ms 65960 KB Output is correct
46 Correct 1037 ms 52684 KB Output is correct
47 Correct 992 ms 50692 KB Output is correct
48 Correct 1051 ms 54364 KB Output is correct
49 Correct 665 ms 66952 KB Output is correct
50 Correct 558 ms 54056 KB Output is correct
51 Correct 935 ms 59100 KB Output is correct
52 Correct 1268 ms 72428 KB Output is correct
53 Correct 1281 ms 77256 KB Output is correct
54 Execution timed out 2079 ms 85448 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 12124 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 12376 KB Output is correct
6 Correct 4 ms 12380 KB Output is correct
7 Correct 4 ms 12376 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 215 ms 40700 KB Output is correct
10 Correct 317 ms 47220 KB Output is correct
11 Correct 290 ms 46336 KB Output is correct
12 Correct 338 ms 48572 KB Output is correct
13 Correct 302 ms 48396 KB Output is correct
14 Correct 217 ms 40764 KB Output is correct
15 Correct 352 ms 49144 KB Output is correct
16 Correct 333 ms 48204 KB Output is correct
17 Correct 355 ms 50228 KB Output is correct
18 Correct 354 ms 50340 KB Output is correct
19 Correct 1072 ms 50412 KB Output is correct
20 Correct 1116 ms 51732 KB Output is correct
21 Correct 1182 ms 50700 KB Output is correct
22 Correct 1056 ms 51580 KB Output is correct
23 Correct 1139 ms 51472 KB Output is correct
24 Correct 1125 ms 49928 KB Output is correct
25 Correct 1073 ms 51048 KB Output is correct
26 Correct 1088 ms 49424 KB Output is correct
27 Correct 5 ms 12388 KB Output is correct
28 Correct 6 ms 12380 KB Output is correct
29 Correct 6 ms 12380 KB Output is correct
30 Correct 5 ms 12380 KB Output is correct
31 Correct 5 ms 12380 KB Output is correct
32 Correct 6 ms 12380 KB Output is correct
33 Correct 6 ms 12468 KB Output is correct
34 Correct 6 ms 12380 KB Output is correct
35 Correct 5 ms 12380 KB Output is correct
36 Correct 38 ms 17500 KB Output is correct
37 Correct 939 ms 53156 KB Output is correct
38 Correct 885 ms 51876 KB Output is correct
39 Correct 881 ms 51104 KB Output is correct
40 Correct 952 ms 50196 KB Output is correct
41 Correct 848 ms 49888 KB Output is correct
42 Correct 798 ms 46496 KB Output is correct
43 Correct 877 ms 52180 KB Output is correct
44 Correct 1051 ms 52604 KB Output is correct
45 Correct 965 ms 53184 KB Output is correct
46 Correct 699 ms 50836 KB Output is correct
47 Execution timed out 2035 ms 16980 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 3 ms 12124 KB Output is correct
6 Correct 4 ms 12376 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12376 KB Output is correct
9 Correct 4 ms 12380 KB Output is correct
10 Correct 215 ms 40700 KB Output is correct
11 Correct 317 ms 47220 KB Output is correct
12 Correct 290 ms 46336 KB Output is correct
13 Correct 338 ms 48572 KB Output is correct
14 Correct 302 ms 48396 KB Output is correct
15 Correct 217 ms 40764 KB Output is correct
16 Correct 352 ms 49144 KB Output is correct
17 Correct 333 ms 48204 KB Output is correct
18 Correct 355 ms 50228 KB Output is correct
19 Correct 354 ms 50340 KB Output is correct
20 Correct 1072 ms 50412 KB Output is correct
21 Correct 1116 ms 51732 KB Output is correct
22 Correct 1182 ms 50700 KB Output is correct
23 Correct 1056 ms 51580 KB Output is correct
24 Correct 1139 ms 51472 KB Output is correct
25 Correct 1125 ms 49928 KB Output is correct
26 Correct 1073 ms 51048 KB Output is correct
27 Correct 1088 ms 49424 KB Output is correct
28 Correct 5 ms 12388 KB Output is correct
29 Correct 6 ms 12380 KB Output is correct
30 Correct 6 ms 12380 KB Output is correct
31 Correct 5 ms 12380 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 12468 KB Output is correct
35 Correct 6 ms 12380 KB Output is correct
36 Correct 5 ms 12380 KB Output is correct
37 Correct 38 ms 17500 KB Output is correct
38 Correct 939 ms 53156 KB Output is correct
39 Correct 885 ms 51876 KB Output is correct
40 Correct 881 ms 51104 KB Output is correct
41 Correct 952 ms 50196 KB Output is correct
42 Correct 848 ms 49888 KB Output is correct
43 Correct 798 ms 46496 KB Output is correct
44 Correct 877 ms 52180 KB Output is correct
45 Correct 1051 ms 52604 KB Output is correct
46 Correct 965 ms 53184 KB Output is correct
47 Correct 699 ms 50836 KB Output is correct
48 Execution timed out 2035 ms 16980 KB Time limit exceeded
49 Halted 0 ms 0 KB -