oj.uz

Submission #547100

# Submission time Handle Problem Language Result Execution time Memory
547100 2022-04-09T14:16:40 Z cig32 Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 40848 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;
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";

  }
  */
}
int getMinimumFuelCapacity(int X, int Y) {
  unordered_map<int, int> omg;
  while(X != root) {
    X = krt[X].par;
    omg[X] = 1;
  }
  while(Y != root) {
    Y = krt[Y].par;
    if(omg[Y] && krt[Y].greenw != 2e9) {
      return krt[Y].greenw;
    }
  }
  return -1;
}

Subtask #1
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 10580 KB Output is correct
4 Correct 6 ms 10600 KB Output is correct
5 Correct 7 ms 10708 KB Output is correct
6 Correct 7 ms 10608 KB Output is correct
7 Correct 8 ms 10720 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 69 ms 21724 KB Output is correct
10 Correct 88 ms 24240 KB Output is correct
11 Correct 89 ms 23972 KB Output is correct
12 Correct 97 ms 24772 KB Output is correct
13 Correct 105 ms 25156 KB Output is correct
14 Correct 136 ms 22108 KB Output is correct
15 Correct 817 ms 28112 KB Output is correct
16 Correct 830 ms 27792 KB Output is correct
17 Correct 888 ms 28676 KB Output is correct
18 Execution timed out 2065 ms 32124 KB Time limit exceeded
19 Halted 0 ms 0 KB -

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 Execution timed out 2086 ms 31472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.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 10580 KB Output is correct
4 Correct 6 ms 10600 KB Output is correct
5 Correct 7 ms 10708 KB Output is correct
6 Correct 7 ms 10608 KB Output is correct
7 Correct 8 ms 10720 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 6 ms 10580 KB Output is correct
10 Correct 8 ms 10708 KB Output is correct
11 Correct 7 ms 10612 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct
13 Correct 7 ms 10632 KB Output is correct
14 Correct 8 ms 10708 KB Output is correct
15 Correct 8 ms 10708 KB Output is correct
16 Correct 7 ms 10736 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 7 ms 10744 KB Output is correct
19 Correct 7 ms 10708 KB Output is correct
20 Correct 7 ms 10736 KB Output is correct
21 Correct 7 ms 10708 KB Output is correct
22 Correct 7 ms 10708 KB Output is correct
23 Correct 7 ms 10608 KB Output is correct
24 Correct 7 ms 10708 KB Output is correct
25 Correct 7 ms 10708 KB Output is correct
26 Correct 7 ms 10708 KB Output is correct
27 Correct 7 ms 10740 KB Output is correct
28 Correct 8 ms 10708 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 6 ms 10580 KB Output is correct
3 Correct 6 ms 10580 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 6 ms 10600 KB Output is correct
6 Correct 7 ms 10708 KB Output is correct
7 Correct 7 ms 10608 KB Output is correct
8 Correct 8 ms 10720 KB Output is correct
9 Correct 7 ms 10708 KB Output is correct
10 Correct 69 ms 21724 KB Output is correct
11 Correct 88 ms 24240 KB Output is correct
12 Correct 89 ms 23972 KB Output is correct
13 Correct 97 ms 24772 KB Output is correct
14 Correct 105 ms 25156 KB Output is correct
15 Correct 8 ms 10708 KB Output is correct
16 Correct 7 ms 10612 KB Output is correct
17 Correct 7 ms 10708 KB Output is correct
18 Correct 7 ms 10632 KB Output is correct
19 Correct 8 ms 10708 KB Output is correct
20 Correct 8 ms 10708 KB Output is correct
21 Correct 7 ms 10736 KB Output is correct
22 Correct 7 ms 10708 KB Output is correct
23 Correct 7 ms 10744 KB Output is correct
24 Correct 7 ms 10708 KB Output is correct
25 Correct 7 ms 10736 KB Output is correct
26 Correct 7 ms 10708 KB Output is correct
27 Correct 7 ms 10708 KB Output is correct
28 Correct 7 ms 10608 KB Output is correct
29 Correct 7 ms 10708 KB Output is correct
30 Correct 7 ms 10708 KB Output is correct
31 Correct 7 ms 10708 KB Output is correct
32 Correct 7 ms 10740 KB Output is correct
33 Correct 8 ms 10708 KB Output is correct
34 Correct 16 ms 12568 KB Output is correct
35 Correct 86 ms 24536 KB Output is correct
36 Correct 97 ms 24616 KB Output is correct
37 Correct 91 ms 24420 KB Output is correct
38 Correct 88 ms 24412 KB Output is correct
39 Correct 88 ms 24228 KB Output is correct
40 Correct 79 ms 23268 KB Output is correct
41 Correct 90 ms 24756 KB Output is correct
42 Correct 93 ms 24552 KB Output is correct
43 Correct 101 ms 24768 KB Output is correct
44 Correct 91 ms 25332 KB Output is correct
45 Runtime error 81 ms 40848 KB Execution killed with signal 11
46 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 10580 KB Output is correct
4 Correct 6 ms 10600 KB Output is correct
5 Correct 7 ms 10708 KB Output is correct
6 Correct 7 ms 10608 KB Output is correct
7 Correct 8 ms 10720 KB Output is correct
8 Correct 7 ms 10708 KB Output is correct
9 Correct 69 ms 21724 KB Output is correct
10 Correct 88 ms 24240 KB Output is correct
11 Correct 89 ms 23972 KB Output is correct
12 Correct 97 ms 24772 KB Output is correct
13 Correct 105 ms 25156 KB Output is correct
14 Correct 136 ms 22108 KB Output is correct
15 Correct 817 ms 28112 KB Output is correct
16 Correct 830 ms 27792 KB Output is correct
17 Correct 888 ms 28676 KB Output is correct
18 Execution timed out 2065 ms 32124 KB Time limit exceeded
19 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 10580 KB Output is correct
5 Correct 6 ms 10600 KB Output is correct
6 Correct 7 ms 10708 KB Output is correct
7 Correct 7 ms 10608 KB Output is correct
8 Correct 8 ms 10720 KB Output is correct
9 Correct 7 ms 10708 KB Output is correct
10 Correct 69 ms 21724 KB Output is correct
11 Correct 88 ms 24240 KB Output is correct
12 Correct 89 ms 23972 KB Output is correct
13 Correct 97 ms 24772 KB Output is correct
14 Correct 105 ms 25156 KB Output is correct
15 Correct 136 ms 22108 KB Output is correct
16 Correct 817 ms 28112 KB Output is correct
17 Correct 830 ms 27792 KB Output is correct
18 Correct 888 ms 28676 KB Output is correct
19 Execution timed out 2065 ms 32124 KB Time limit exceeded
20 Halted 0 ms 0 KB -