oj.uz

Submission #547101

# Submission time Handle Problem Language Result Execution time Memory
547101 2022-04-09T14:23:32 Z cig32 Swapping Cities (APIO20_swap) C++17
6 / 100
 228 ms 69180 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(x);
    }
  }
}
int l[202020], r[202020];
pair<int,int> st[19][202020];
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;
  /*
  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";

  }
  */
  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))]);
    }
  }
}
int getMinimumFuelCapacity(int X, int Y) {
  int q = lca_idx(X, Y);
  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:163:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   for(int i=0; i<euler.size(); i++) r[euler[i]] = i;
      |                ~^~~~~~~~~~~~~
swap.cpp:165:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |   for(int i=0; i<euler.size(); i++) st[0][i] = {dep[euler[i]], euler[i]};
      |                ~^~~~~~~~~~~~~
swap.cpp:167:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int j=0; j<euler.size(); j++) {
      |                  ~^~~~~~~~~~~~~
swap.cpp:168:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |       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 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10640 KB Output is correct
4 Correct 6 ms 10808 KB Output is correct
5 Correct 6 ms 11080 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11236 KB Output is correct
8 Correct 7 ms 11220 KB Output is correct
9 Correct 118 ms 53492 KB Output is correct
10 Correct 165 ms 57220 KB Output is correct
11 Correct 132 ms 56892 KB Output is correct
12 Correct 144 ms 57928 KB Output is correct
13 Correct 166 ms 61824 KB Output is correct
14 Correct 145 ms 53616 KB Output is correct
15 Correct 197 ms 58936 KB Output is correct
16 Correct 194 ms 58432 KB Output is correct
17 Correct 228 ms 59528 KB Output is correct
18 Correct 183 ms 63420 KB Output is correct
19 Correct 75 ms 26100 KB Output is correct
20 Correct 225 ms 63052 KB Output is correct
21 Correct 193 ms 62360 KB Output is correct
22 Correct 202 ms 63992 KB Output is correct
23 Correct 211 ms 69180 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Incorrect 163 ms 66536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10640 KB Output is correct
4 Correct 6 ms 10808 KB Output is correct
5 Correct 6 ms 11080 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11236 KB Output is correct
8 Correct 7 ms 11220 KB Output is correct
9 Correct 6 ms 10580 KB Output is correct
10 Incorrect 7 ms 11240 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 6 ms 10640 KB Output is correct
5 Correct 6 ms 10808 KB Output is correct
6 Correct 6 ms 11080 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 8 ms 11236 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 118 ms 53492 KB Output is correct
11 Correct 165 ms 57220 KB Output is correct
12 Correct 132 ms 56892 KB Output is correct
13 Correct 144 ms 57928 KB Output is correct
14 Correct 166 ms 61824 KB Output is correct
15 Incorrect 7 ms 11240 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10640 KB Output is correct
4 Correct 6 ms 10808 KB Output is correct
5 Correct 6 ms 11080 KB Output is correct
6 Correct 7 ms 11092 KB Output is correct
7 Correct 8 ms 11236 KB Output is correct
8 Correct 7 ms 11220 KB Output is correct
9 Correct 118 ms 53492 KB Output is correct
10 Correct 165 ms 57220 KB Output is correct
11 Correct 132 ms 56892 KB Output is correct
12 Correct 144 ms 57928 KB Output is correct
13 Correct 166 ms 61824 KB Output is correct
14 Correct 145 ms 53616 KB Output is correct
15 Correct 197 ms 58936 KB Output is correct
16 Correct 194 ms 58432 KB Output is correct
17 Correct 228 ms 59528 KB Output is correct
18 Correct 183 ms 63420 KB Output is correct
19 Incorrect 163 ms 66536 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 6 ms 10640 KB Output is correct
5 Correct 6 ms 10808 KB Output is correct
6 Correct 6 ms 11080 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 8 ms 11236 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 118 ms 53492 KB Output is correct
11 Correct 165 ms 57220 KB Output is correct
12 Correct 132 ms 56892 KB Output is correct
13 Correct 144 ms 57928 KB Output is correct
14 Correct 166 ms 61824 KB Output is correct
15 Correct 145 ms 53616 KB Output is correct
16 Correct 197 ms 58936 KB Output is correct
17 Correct 194 ms 58432 KB Output is correct
18 Correct 228 ms 59528 KB Output is correct
19 Correct 183 ms 63420 KB Output is correct
20 Incorrect 163 ms 66536 KB Output isn't correct
21 Halted 0 ms 0 KB -