oj.uz

Submission #547110

# Submission time Handle Problem Language Result Execution time Memory
547110 2022-04-09T14:50:12 Z cig32 Swapping Cities (APIO20_swap) C++17
53 / 100
 235 ms 96128 KB 
#include "bits/stdc++.h"
using namespace std;
//#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
int fastlog(int x) {
  if(x == 0) return -1;
  return 32 - __builtin_clz(x) - 1;
}
void gay(int i) {
  cout << "Case #" << i << ": ";
}
#include "swap.h"
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W);

int getMinimumFuelCapacity(int X, int Y);

int n, m;
vector<pair<int,int> > adj[101010];
struct edge {
  int f, t, w;
};
class cmp {
  public:
  bool operator() (edge x, edge y) {
    return x.w>y.w;
  }
};
vector<edge> mst;
edge e[101010];
int dsu[101010];
int set_of(int u) {
  if(dsu[u]==u) return u;
  return dsu[u]= set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
struct node {
  vector<int> a; // children
  int par; // parenty
  int blackw, greenw; // minimum weight limit s.t. subtree is pairwise reachable
  int madeg = 0; // max degree
} krt[202020];
int rep[202020];
int root;
vector<int> euler;
int dep[202020];
int fuck[202020];
void dfs(int node, int prv) {
  euler.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  fuck[node] = min(krt[node].greenw, (prv == -1 ? (int)2e9 : fuck[prv]));
  for(int x: krt[node].a) {
    if(x != prv) {
      dfs(x, node);
      euler.push_back(node);
    }
  }
}
int l[202020], r[202020];
pair<int,int> st[19][404040];
int lca_idx(int x, int y) {
  int m1 = min(l[x], l[y]);
  int m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2-m1 + 1) - 1;
  return min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N, m = M;
  for(int i=0; i<m; i++) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
    e[i] = {U[i], V[i], W[i]};
  }
  for(int i=0; i<n; i++) dsu[i] = i;
  priority_queue<edge, vector<edge>, cmp> pq;
  for(int i=0; i<m; i++) pq.push(e[i]);
  int newnode = n;
  for(int i=0; i<n; i++) rep[i] = i;
  for(int i=0; i<202020; i++) krt[i].blackw = 0, krt[i].greenw = 2e9, krt[i].par = -1;
  int deg[n];
  for(int i=0; i<n; i++) deg[i] = 0;
  // Conditions: either cycle or max degree ≥ 3 (i.e. NOT chain)
  while(pq.size()) {
    deg[pq.top().f]++;
    deg[pq.top().t]++;
    if(set_of(pq.top().f) != set_of(pq.top().t)) {
      int st1 = rep[set_of(pq.top().f)];
      int st2 = rep[set_of(pq.top().t)];
      krt[newnode].a.push_back(st1);
      krt[newnode].a.push_back(st2);
      krt[st1].par = krt[st2].par = newnode;
      union_(pq.top().f, pq.top().t);
      rep[set_of(pq.top().f)] = newnode;
      krt[newnode].madeg = max({krt[st1].madeg, krt[st2].madeg, deg[pq.top().f], deg[pq.top().t]});
      krt[newnode].blackw = pq.top().w;
      if(krt[newnode].madeg >= 3 || krt[st1].greenw != 2e9 || krt[st2].greenw != 2e9) {
        krt[newnode].greenw = pq.top().w;
      }
      else {
        krt[newnode].greenw = 2e9;
      }
      newnode++;
    }
    else { // update all the way to the root, update max degree array and green weights
      int rt = rep[set_of(pq.top().f)];
      //cout << "root = " << rt << "\n";
      if(krt[rt].greenw == 2e9) { // O(component size) is ok
        int now = pq.top().f;
        unordered_map<int, int> vis;
        while(now != rt) {
          now = krt[now].par;
          vis[now] = 1;
        }
        now = pq.top().t;
        while(now != rt) {
          now = krt[now].par;
          if(vis[now]) {
            // common ancestor
            krt[now].greenw = pq.top().w;
          }
        }
      }

    }
    pq.pop();
  }
  root = newnode - 1;
  
  dfs(root, -1);
  for(int i=0; i<euler.size(); i++) r[euler[i]] = i;
  for(int i=euler.size()-1; i>=0; i--) l[euler[i]] = i;
  for(int i=0; i<euler.size(); i++) st[0][i] = {dep[euler[i]], euler[i]};
  for(int i=1; i<19; i++) {
    for(int j=0; j<euler.size(); j++) {
      if(j+(1<<i)-1 < euler.size()) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  /*
  
  cout << "Root = " << root << "\n";
  cout << "Euler tour = ";
  for(int x: euler) cout << x << " ";
  cout << "\n";
  for(int i=newnode - 1; i >= 0; i--) {
    cout << "node " << i << ": black = " << krt[i].blackw << ", green = " << krt[i].greenw << ", max degree = " << krt[i].madeg << "\n";
    for(int x: krt[i].a) cout << i << " " << x << "\n";

  }
  
  
  cout << "test " << min(l[2], l[4]) << " " << max(r[2], r[4]) << "\n";
  */
}
int getMinimumFuelCapacity(int X, int Y) {
  int q = lca_idx(X, Y);
  //cout << "lca = " << q << "\n";
  return (fuck[q] == 2e9 ? -1 : fuck[q]);
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |   for(int i=0; i<euler.size(); i++) r[euler[i]] = i;
      |                ~^~~~~~~~~~~~~
swap.cpp:159:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   for(int i=0; i<euler.size(); i++) st[0][i] = {dep[euler[i]], euler[i]};
      |                ~^~~~~~~~~~~~~
swap.cpp:161:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int j=0; j<euler.size(); j++) {
      |                  ~^~~~~~~~~~~~~
swap.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |       if(j+(1<<i)-1 < euler.size()) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 8 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 11220 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 9 ms 11220 KB Output is correct
9 Correct 124 ms 67496 KB Output is correct
10 Correct 144 ms 80844 KB Output is correct
11 Correct 146 ms 79908 KB Output is correct
12 Correct 163 ms 83836 KB Output is correct
13 Correct 150 ms 87032 KB Output is correct
14 Correct 122 ms 67456 KB Output is correct
15 Correct 199 ms 82956 KB Output is correct
16 Correct 198 ms 80960 KB Output is correct
17 Correct 218 ms 85532 KB Output is correct
18 Correct 233 ms 88752 KB Output is correct
19 Correct 71 ms 24196 KB Output is correct
20 Correct 208 ms 83328 KB Output is correct
21 Correct 202 ms 80300 KB Output is correct
22 Correct 219 ms 85444 KB Output is correct
23 Correct 235 ms 89928 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 8 ms 10580 KB Output is correct
3 Correct 172 ms 88000 KB Output is correct
4 Correct 192 ms 96128 KB Output is correct
5 Correct 173 ms 93240 KB Output is correct
6 Correct 192 ms 95712 KB Output is correct
7 Correct 187 ms 94600 KB Output is correct
8 Correct 183 ms 91032 KB Output is correct
9 Correct 187 ms 94020 KB Output is correct
10 Correct 177 ms 90196 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 8 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 11220 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 9 ms 11220 KB Output is correct
9 Correct 6 ms 10580 KB Output is correct
10 Correct 8 ms 11252 KB Output is correct
11 Correct 7 ms 11188 KB Output is correct
12 Correct 7 ms 11220 KB Output is correct
13 Correct 8 ms 11092 KB Output is correct
14 Correct 6 ms 11092 KB Output is correct
15 Correct 8 ms 11220 KB Output is correct
16 Correct 8 ms 11220 KB Output is correct
17 Correct 7 ms 11268 KB Output is correct
18 Correct 10 ms 11220 KB Output is correct
19 Correct 7 ms 11092 KB Output is correct
20 Correct 8 ms 11220 KB Output is correct
21 Correct 8 ms 11220 KB Output is correct
22 Correct 7 ms 10836 KB Output is correct
23 Correct 8 ms 11084 KB Output is correct
24 Correct 8 ms 11220 KB Output is correct
25 Correct 8 ms 11220 KB Output is correct
26 Correct 8 ms 11204 KB Output is correct
27 Correct 7 ms 11220 KB Output is correct
28 Correct 8 ms 11220 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 8 ms 10580 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 7 ms 10836 KB Output is correct
6 Correct 7 ms 11220 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 9 ms 11220 KB Output is correct
10 Correct 124 ms 67496 KB Output is correct
11 Correct 144 ms 80844 KB Output is correct
12 Correct 146 ms 79908 KB Output is correct
13 Correct 163 ms 83836 KB Output is correct
14 Correct 150 ms 87032 KB Output is correct
15 Correct 8 ms 11252 KB Output is correct
16 Correct 7 ms 11188 KB Output is correct
17 Correct 7 ms 11220 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 6 ms 11092 KB Output is correct
20 Correct 8 ms 11220 KB Output is correct
21 Correct 8 ms 11220 KB Output is correct
22 Correct 7 ms 11268 KB Output is correct
23 Correct 10 ms 11220 KB Output is correct
24 Correct 7 ms 11092 KB Output is correct
25 Correct 8 ms 11220 KB Output is correct
26 Correct 8 ms 11220 KB Output is correct
27 Correct 7 ms 10836 KB Output is correct
28 Correct 8 ms 11084 KB Output is correct
29 Correct 8 ms 11220 KB Output is correct
30 Correct 8 ms 11220 KB Output is correct
31 Correct 8 ms 11204 KB Output is correct
32 Correct 7 ms 11220 KB Output is correct
33 Correct 8 ms 11220 KB Output is correct
34 Correct 21 ms 19440 KB Output is correct
35 Correct 152 ms 83936 KB Output is correct
36 Correct 161 ms 83832 KB Output is correct
37 Correct 152 ms 83908 KB Output is correct
38 Correct 141 ms 82824 KB Output is correct
39 Correct 161 ms 82532 KB Output is correct
40 Correct 139 ms 76348 KB Output is correct
41 Correct 155 ms 84016 KB Output is correct
42 Correct 155 ms 83924 KB Output is correct
43 Correct 138 ms 88000 KB Output is correct
44 Correct 147 ms 84420 KB Output is correct
45 Runtime error 79 ms 37756 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 8 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 11220 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 9 ms 11220 KB Output is correct
9 Correct 124 ms 67496 KB Output is correct
10 Correct 144 ms 80844 KB Output is correct
11 Correct 146 ms 79908 KB Output is correct
12 Correct 163 ms 83836 KB Output is correct
13 Correct 150 ms 87032 KB Output is correct
14 Correct 122 ms 67456 KB Output is correct
15 Correct 199 ms 82956 KB Output is correct
16 Correct 198 ms 80960 KB Output is correct
17 Correct 218 ms 85532 KB Output is correct
18 Correct 233 ms 88752 KB Output is correct
19 Correct 172 ms 88000 KB Output is correct
20 Correct 192 ms 96128 KB Output is correct
21 Correct 173 ms 93240 KB Output is correct
22 Correct 192 ms 95712 KB Output is correct
23 Correct 187 ms 94600 KB Output is correct
24 Correct 183 ms 91032 KB Output is correct
25 Correct 187 ms 94020 KB Output is correct
26 Correct 177 ms 90196 KB Output is correct
27 Correct 8 ms 11252 KB Output is correct
28 Correct 7 ms 11188 KB Output is correct
29 Correct 7 ms 11220 KB Output is correct
30 Correct 8 ms 11092 KB Output is correct
31 Correct 6 ms 11092 KB Output is correct
32 Correct 8 ms 11220 KB Output is correct
33 Correct 8 ms 11220 KB Output is correct
34 Correct 7 ms 11268 KB Output is correct
35 Correct 10 ms 11220 KB Output is correct
36 Correct 21 ms 19440 KB Output is correct
37 Correct 152 ms 83936 KB Output is correct
38 Correct 161 ms 83832 KB Output is correct
39 Correct 152 ms 83908 KB Output is correct
40 Correct 141 ms 82824 KB Output is correct
41 Correct 161 ms 82532 KB Output is correct
42 Correct 139 ms 76348 KB Output is correct
43 Correct 155 ms 84016 KB Output is correct
44 Correct 155 ms 83924 KB Output is correct
45 Correct 138 ms 88000 KB Output is correct
46 Correct 147 ms 84420 KB Output is correct
47 Correct 29 ms 19272 KB Output is correct
48 Correct 213 ms 89604 KB Output is correct
49 Correct 209 ms 89696 KB Output is correct
50 Correct 213 ms 89440 KB Output is correct
51 Correct 206 ms 88968 KB Output is correct
52 Correct 207 ms 84424 KB Output is correct
53 Correct 158 ms 64068 KB Output is correct
54 Correct 219 ms 89836 KB Output is correct
55 Correct 207 ms 89608 KB Output is correct
56 Correct 194 ms 92792 KB Output is correct
57 Correct 210 ms 90428 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 5 ms 10580 KB Output is correct
3 Correct 8 ms 10580 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 7 ms 10836 KB Output is correct
6 Correct 7 ms 11220 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 9 ms 11220 KB Output is correct
10 Correct 124 ms 67496 KB Output is correct
11 Correct 144 ms 80844 KB Output is correct
12 Correct 146 ms 79908 KB Output is correct
13 Correct 163 ms 83836 KB Output is correct
14 Correct 150 ms 87032 KB Output is correct
15 Correct 122 ms 67456 KB Output is correct
16 Correct 199 ms 82956 KB Output is correct
17 Correct 198 ms 80960 KB Output is correct
18 Correct 218 ms 85532 KB Output is correct
19 Correct 233 ms 88752 KB Output is correct
20 Correct 172 ms 88000 KB Output is correct
21 Correct 192 ms 96128 KB Output is correct
22 Correct 173 ms 93240 KB Output is correct
23 Correct 192 ms 95712 KB Output is correct
24 Correct 187 ms 94600 KB Output is correct
25 Correct 183 ms 91032 KB Output is correct
26 Correct 187 ms 94020 KB Output is correct
27 Correct 177 ms 90196 KB Output is correct
28 Correct 8 ms 11252 KB Output is correct
29 Correct 7 ms 11188 KB Output is correct
30 Correct 7 ms 11220 KB Output is correct
31 Correct 8 ms 11092 KB Output is correct
32 Correct 6 ms 11092 KB Output is correct
33 Correct 8 ms 11220 KB Output is correct
34 Correct 8 ms 11220 KB Output is correct
35 Correct 7 ms 11268 KB Output is correct
36 Correct 10 ms 11220 KB Output is correct
37 Correct 21 ms 19440 KB Output is correct
38 Correct 152 ms 83936 KB Output is correct
39 Correct 161 ms 83832 KB Output is correct
40 Correct 152 ms 83908 KB Output is correct
41 Correct 141 ms 82824 KB Output is correct
42 Correct 161 ms 82532 KB Output is correct
43 Correct 139 ms 76348 KB Output is correct
44 Correct 155 ms 84016 KB Output is correct
45 Correct 155 ms 83924 KB Output is correct
46 Correct 138 ms 88000 KB Output is correct
47 Correct 147 ms 84420 KB Output is correct
48 Correct 29 ms 19272 KB Output is correct
49 Correct 213 ms 89604 KB Output is correct
50 Correct 209 ms 89696 KB Output is correct
51 Correct 213 ms 89440 KB Output is correct
52 Correct 206 ms 88968 KB Output is correct
53 Correct 207 ms 84424 KB Output is correct
54 Correct 158 ms 64068 KB Output is correct
55 Correct 219 ms 89836 KB Output is correct
56 Correct 207 ms 89608 KB Output is correct
57 Correct 194 ms 92792 KB Output is correct
58 Correct 210 ms 90428 KB Output is correct
59 Correct 71 ms 24196 KB Output is correct
60 Correct 208 ms 83328 KB Output is correct
61 Correct 202 ms 80300 KB Output is correct
62 Correct 219 ms 85444 KB Output is correct
63 Correct 235 ms 89928 KB Output is correct
64 Correct 7 ms 11092 KB Output is correct
65 Correct 8 ms 11220 KB Output is correct
66 Correct 8 ms 11220 KB Output is correct
67 Correct 7 ms 10836 KB Output is correct
68 Correct 8 ms 11084 KB Output is correct
69 Correct 8 ms 11220 KB Output is correct
70 Correct 8 ms 11220 KB Output is correct
71 Correct 8 ms 11204 KB Output is correct
72 Correct 7 ms 11220 KB Output is correct
73 Correct 8 ms 11220 KB Output is correct
74 Runtime error 79 ms 37756 KB Execution killed with signal 11
75 Halted 0 ms 0 KB -