oj.uz

Submission #567604

# Submission time Handle Problem Language Result Execution time Memory
567604 2022-05-23T19:27:10 Z farhan132 Swapping Cities (APIO20_swap) C++17
100 / 100
 862 ms 94176 KB 
#include "swap.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 3e5 + 15;

ll par[N], ok[N], n, val[N], pr[20][N];
ii p[N];
vector < ll > v[N];

ll find(ll a){
  if(a == par[a]) return a;
  return par[a] = find(par[a]);
}
ll eq(ii x, ii y){
  if(x == y || x == make_pair(y.ss, y.ff)) return 1;
  return 0; 
}
void merge(ll x, ll y, ll ww){
  ii w = {x, y};

  x = find(x);

  y = find(y);

  ++n;
  val[n] = ww;
  ok[n] = (ok[x] & ok[y]);


  par[x] = par[y] = n;
  par[n] = n;
  v[n].pb(x);
  if(x != y) v[n].pb(y);
  
  if(ok[n]){
    if(x == y){
      ok[n] = 0;
    }else{
      bool f = 0;
      ii wut;
      for(auto z1 : {p[x].ff, p[x].ss}){
        for(auto z2 : {p[y].ff, p[y].ss}){
          if(eq(w, {z1, z2})) f = 1, wut = {z1, z2};
        }
      }
      if(!f){
        ok[n] = 0;
      }else{
        if(wut.ff == p[x].ff) p[n].ff = p[x].ss;
        else p[n].ff = p[x].ff;
        if(wut.ss == p[y].ff) p[n].ss = p[y].ss;
        else p[n].ss = p[y].ff;
      }
    }
  }
  
  return;
}
ll d[N];
void dfs(ll s, ll _p, ll dp){
  pr[0][s] = _p;
  d[s] = dp;
  for(ll i = 1; i < 20; i++) pr[i][s] = pr[i-1][pr[i-1][s]];
  for(auto u : v[s]){
    dfs(u, s, dp + 1);
  }
  return;
}
ll lca(ll x, ll y){
  if(d[x] < d[y]) swap(x, y);
  for(ll i = 19; i >= 0; i--){
    if(d[x] - (1 << i) >= d[y]) x = pr[i][x];
  }
  if(x == y) return x;
  for(ll i = 19; i >= 0; i--){
    if(pr[i][x] == pr[i][y]) continue;
    x = pr[i][x], y = pr[i][y];
  }
  return pr[0][x];
}

void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
  n = _n;
  vector < tuple < ll , ll , ll > > e;
  for(ll i = 0; i < m; i++) e.pb({W[i], V[i]+1, U[i]+1});
  for(ll i = 1; i <= n; i++){
    par[i] = i;
    p[i] = {i, i};
    ok[i] = 1;
  }

  sort(e.begin(), e.end());
  for(auto [w, x, y] : e){
    merge(x, y, w);
  }
  dfs(n, n, 1);
  return;
}

int getMinimumFuelCapacity(int x, int y) {
  x++; y++;
  if(ok[n] == 1) return -1;

  ll cur = lca(x, y);
  if(!ok[cur]) return val[cur];
  for(ll i = 19; i >= 0; i--){
    if(!ok[pr[i][cur]]) continue;
    cur = pr[i][cur];
  }
  cur = pr[0][cur];
  return val[cur];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7996 KB Output is correct
8 Correct 5 ms 8020 KB Output is correct
9 Correct 103 ms 45748 KB Output is correct
10 Correct 130 ms 54204 KB Output is correct
11 Correct 136 ms 53272 KB Output is correct
12 Correct 134 ms 55964 KB Output is correct
13 Correct 118 ms 58344 KB Output is correct
14 Correct 112 ms 45740 KB Output is correct
15 Correct 202 ms 56160 KB Output is correct
16 Correct 177 ms 54760 KB Output is correct
17 Correct 199 ms 57708 KB Output is correct
18 Correct 172 ms 59912 KB Output is correct
19 Correct 219 ms 18940 KB Output is correct
20 Correct 585 ms 56372 KB Output is correct
21 Correct 620 ms 54408 KB Output is correct
22 Correct 636 ms 57760 KB Output is correct
23 Correct 705 ms 60176 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 667 ms 57860 KB Output is correct
4 Correct 630 ms 60384 KB Output is correct
5 Correct 714 ms 58460 KB Output is correct
6 Correct 678 ms 59992 KB Output is correct
7 Correct 680 ms 59264 KB Output is correct
8 Correct 676 ms 57052 KB Output is correct
9 Correct 671 ms 58984 KB Output is correct
10 Correct 685 ms 56612 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7996 KB Output is correct
8 Correct 5 ms 8020 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 5 ms 8020 KB Output is correct
11 Correct 5 ms 8020 KB Output is correct
12 Correct 5 ms 7916 KB Output is correct
13 Correct 5 ms 7880 KB Output is correct
14 Correct 5 ms 7884 KB Output is correct
15 Correct 5 ms 8020 KB Output is correct
16 Correct 5 ms 8020 KB Output is correct
17 Correct 5 ms 8012 KB Output is correct
18 Correct 5 ms 8020 KB Output is correct
19 Correct 6 ms 7904 KB Output is correct
20 Correct 6 ms 8020 KB Output is correct
21 Correct 5 ms 8020 KB Output is correct
22 Correct 5 ms 8148 KB Output is correct
23 Correct 5 ms 7892 KB Output is correct
24 Correct 6 ms 8276 KB Output is correct
25 Correct 5 ms 8276 KB Output is correct
26 Correct 6 ms 8276 KB Output is correct
27 Correct 6 ms 8020 KB Output is correct
28 Correct 5 ms 8276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 4 ms 7636 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7892 KB Output is correct
8 Correct 5 ms 7996 KB Output is correct
9 Correct 5 ms 8020 KB Output is correct
10 Correct 103 ms 45748 KB Output is correct
11 Correct 130 ms 54204 KB Output is correct
12 Correct 136 ms 53272 KB Output is correct
13 Correct 134 ms 55964 KB Output is correct
14 Correct 118 ms 58344 KB Output is correct
15 Correct 5 ms 8020 KB Output is correct
16 Correct 5 ms 8020 KB Output is correct
17 Correct 5 ms 7916 KB Output is correct
18 Correct 5 ms 7880 KB Output is correct
19 Correct 5 ms 7884 KB Output is correct
20 Correct 5 ms 8020 KB Output is correct
21 Correct 5 ms 8020 KB Output is correct
22 Correct 5 ms 8012 KB Output is correct
23 Correct 5 ms 8020 KB Output is correct
24 Correct 6 ms 7904 KB Output is correct
25 Correct 6 ms 8020 KB Output is correct
26 Correct 5 ms 8020 KB Output is correct
27 Correct 5 ms 8148 KB Output is correct
28 Correct 5 ms 7892 KB Output is correct
29 Correct 6 ms 8276 KB Output is correct
30 Correct 5 ms 8276 KB Output is correct
31 Correct 6 ms 8276 KB Output is correct
32 Correct 6 ms 8020 KB Output is correct
33 Correct 5 ms 8276 KB Output is correct
34 Correct 15 ms 14432 KB Output is correct
35 Correct 127 ms 57024 KB Output is correct
36 Correct 139 ms 57008 KB Output is correct
37 Correct 139 ms 56932 KB Output is correct
38 Correct 129 ms 56248 KB Output is correct
39 Correct 129 ms 56000 KB Output is correct
40 Correct 128 ms 51928 KB Output is correct
41 Correct 138 ms 57272 KB Output is correct
42 Correct 129 ms 57004 KB Output is correct
43 Correct 111 ms 60072 KB Output is correct
44 Correct 135 ms 57364 KB Output is correct
45 Correct 168 ms 71168 KB Output is correct
46 Correct 143 ms 57148 KB Output is correct
47 Correct 132 ms 57000 KB Output is correct
48 Correct 141 ms 61572 KB Output is correct
49 Correct 105 ms 59820 KB Output is correct
50 Correct 80 ms 48940 KB Output is correct
51 Correct 131 ms 62180 KB Output is correct
52 Correct 194 ms 77812 KB Output is correct
53 Correct 210 ms 82608 KB Output is correct
54 Correct 211 ms 90312 KB Output is correct
55 Correct 111 ms 59744 KB Output is correct
56 Correct 205 ms 83336 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7996 KB Output is correct
8 Correct 5 ms 8020 KB Output is correct
9 Correct 103 ms 45748 KB Output is correct
10 Correct 130 ms 54204 KB Output is correct
11 Correct 136 ms 53272 KB Output is correct
12 Correct 134 ms 55964 KB Output is correct
13 Correct 118 ms 58344 KB Output is correct
14 Correct 112 ms 45740 KB Output is correct
15 Correct 202 ms 56160 KB Output is correct
16 Correct 177 ms 54760 KB Output is correct
17 Correct 199 ms 57708 KB Output is correct
18 Correct 172 ms 59912 KB Output is correct
19 Correct 667 ms 57860 KB Output is correct
20 Correct 630 ms 60384 KB Output is correct
21 Correct 714 ms 58460 KB Output is correct
22 Correct 678 ms 59992 KB Output is correct
23 Correct 680 ms 59264 KB Output is correct
24 Correct 676 ms 57052 KB Output is correct
25 Correct 671 ms 58984 KB Output is correct
26 Correct 685 ms 56612 KB Output is correct
27 Correct 5 ms 8020 KB Output is correct
28 Correct 5 ms 8020 KB Output is correct
29 Correct 5 ms 7916 KB Output is correct
30 Correct 5 ms 7880 KB Output is correct
31 Correct 5 ms 7884 KB Output is correct
32 Correct 5 ms 8020 KB Output is correct
33 Correct 5 ms 8020 KB Output is correct
34 Correct 5 ms 8012 KB Output is correct
35 Correct 5 ms 8020 KB Output is correct
36 Correct 15 ms 14432 KB Output is correct
37 Correct 127 ms 57024 KB Output is correct
38 Correct 139 ms 57008 KB Output is correct
39 Correct 139 ms 56932 KB Output is correct
40 Correct 129 ms 56248 KB Output is correct
41 Correct 129 ms 56000 KB Output is correct
42 Correct 128 ms 51928 KB Output is correct
43 Correct 138 ms 57272 KB Output is correct
44 Correct 129 ms 57004 KB Output is correct
45 Correct 111 ms 60072 KB Output is correct
46 Correct 135 ms 57364 KB Output is correct
47 Correct 33 ms 14032 KB Output is correct
48 Correct 598 ms 60932 KB Output is correct
49 Correct 584 ms 60828 KB Output is correct
50 Correct 574 ms 60732 KB Output is correct
51 Correct 534 ms 60452 KB Output is correct
52 Correct 489 ms 57612 KB Output is correct
53 Correct 397 ms 44800 KB Output is correct
54 Correct 601 ms 61228 KB Output is correct
55 Correct 628 ms 60880 KB Output is correct
56 Correct 661 ms 63288 KB Output is correct
57 Correct 494 ms 61240 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 4 ms 7636 KB Output is correct
6 Correct 5 ms 7892 KB Output is correct
7 Correct 5 ms 7892 KB Output is correct
8 Correct 5 ms 7996 KB Output is correct
9 Correct 5 ms 8020 KB Output is correct
10 Correct 103 ms 45748 KB Output is correct
11 Correct 130 ms 54204 KB Output is correct
12 Correct 136 ms 53272 KB Output is correct
13 Correct 134 ms 55964 KB Output is correct
14 Correct 118 ms 58344 KB Output is correct
15 Correct 112 ms 45740 KB Output is correct
16 Correct 202 ms 56160 KB Output is correct
17 Correct 177 ms 54760 KB Output is correct
18 Correct 199 ms 57708 KB Output is correct
19 Correct 172 ms 59912 KB Output is correct
20 Correct 667 ms 57860 KB Output is correct
21 Correct 630 ms 60384 KB Output is correct
22 Correct 714 ms 58460 KB Output is correct
23 Correct 678 ms 59992 KB Output is correct
24 Correct 680 ms 59264 KB Output is correct
25 Correct 676 ms 57052 KB Output is correct
26 Correct 671 ms 58984 KB Output is correct
27 Correct 685 ms 56612 KB Output is correct
28 Correct 5 ms 8020 KB Output is correct
29 Correct 5 ms 8020 KB Output is correct
30 Correct 5 ms 7916 KB Output is correct
31 Correct 5 ms 7880 KB Output is correct
32 Correct 5 ms 7884 KB Output is correct
33 Correct 5 ms 8020 KB Output is correct
34 Correct 5 ms 8020 KB Output is correct
35 Correct 5 ms 8012 KB Output is correct
36 Correct 5 ms 8020 KB Output is correct
37 Correct 15 ms 14432 KB Output is correct
38 Correct 127 ms 57024 KB Output is correct
39 Correct 139 ms 57008 KB Output is correct
40 Correct 139 ms 56932 KB Output is correct
41 Correct 129 ms 56248 KB Output is correct
42 Correct 129 ms 56000 KB Output is correct
43 Correct 128 ms 51928 KB Output is correct
44 Correct 138 ms 57272 KB Output is correct
45 Correct 129 ms 57004 KB Output is correct
46 Correct 111 ms 60072 KB Output is correct
47 Correct 135 ms 57364 KB Output is correct
48 Correct 33 ms 14032 KB Output is correct
49 Correct 598 ms 60932 KB Output is correct
50 Correct 584 ms 60828 KB Output is correct
51 Correct 574 ms 60732 KB Output is correct
52 Correct 534 ms 60452 KB Output is correct
53 Correct 489 ms 57612 KB Output is correct
54 Correct 397 ms 44800 KB Output is correct
55 Correct 601 ms 61228 KB Output is correct
56 Correct 628 ms 60880 KB Output is correct
57 Correct 661 ms 63288 KB Output is correct
58 Correct 494 ms 61240 KB Output is correct
59 Correct 219 ms 18940 KB Output is correct
60 Correct 585 ms 56372 KB Output is correct
61 Correct 620 ms 54408 KB Output is correct
62 Correct 636 ms 57760 KB Output is correct
63 Correct 705 ms 60176 KB Output is correct
64 Correct 6 ms 7904 KB Output is correct
65 Correct 6 ms 8020 KB Output is correct
66 Correct 5 ms 8020 KB Output is correct
67 Correct 5 ms 8148 KB Output is correct
68 Correct 5 ms 7892 KB Output is correct
69 Correct 6 ms 8276 KB Output is correct
70 Correct 5 ms 8276 KB Output is correct
71 Correct 6 ms 8276 KB Output is correct
72 Correct 6 ms 8020 KB Output is correct
73 Correct 5 ms 8276 KB Output is correct
74 Correct 168 ms 71168 KB Output is correct
75 Correct 143 ms 57148 KB Output is correct
76 Correct 132 ms 57000 KB Output is correct
77 Correct 141 ms 61572 KB Output is correct
78 Correct 105 ms 59820 KB Output is correct
79 Correct 80 ms 48940 KB Output is correct
80 Correct 131 ms 62180 KB Output is correct
81 Correct 194 ms 77812 KB Output is correct
82 Correct 210 ms 82608 KB Output is correct
83 Correct 211 ms 90312 KB Output is correct
84 Correct 111 ms 59744 KB Output is correct
85 Correct 205 ms 83336 KB Output is correct
86 Correct 211 ms 30836 KB Output is correct
87 Correct 533 ms 60836 KB Output is correct
88 Correct 537 ms 60800 KB Output is correct
89 Correct 709 ms 62848 KB Output is correct
90 Correct 235 ms 66400 KB Output is correct
91 Correct 287 ms 62500 KB Output is correct
92 Correct 707 ms 64056 KB Output is correct
93 Correct 637 ms 80844 KB Output is correct
94 Correct 862 ms 86056 KB Output is correct
95 Correct 741 ms 94176 KB Output is correct
96 Correct 654 ms 63440 KB Output is correct
97 Correct 758 ms 74692 KB Output is correct