oj.uz

Submission #747700

# Submission time Handle Problem Language Result Execution time Memory
747700 2023-05-24T13:41:44 Z Szil Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 517768 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

struct Edge {
  int u, v, w;

  Edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}
};

struct DSU {

  struct Save {
    int idx, a, b, sz;

    Save(int idx_, int a_, int b_, int sz_) : idx(idx_), a(a_), b(b_), sz(sz_) {}
  };

  vector<int> a, b, sz;
  int n = 0;
  bool init;
  stack<Save> st;

  DSU() {
    init = false;
  }

  DSU(DSU &cc) {
    n = cc.n;
    a.resize(n);
    b.resize(n);
    sz.resize(n);
    init = true;
    for (int i = 0; i < n; i++) {
      a[i] = cc.a[i];
      b[i] = cc.b[i];
      sz[i] = cc.sz[i];
    }
  }

  DSU(int n_) : n(n_) {
    a.resize(n);
    b.resize(n);
    sz.resize(n);
    init = true;
    for (int i = 0; i < n; i++) {
      a[i] = i;
      b[i] = i;
      sz[i] = 1;
    }
  }

  int get(int u) {
    return a[u]==u?u:get(a[u]);
  }

  void unio(int u, int v) {
    int ulead = get(u), vlead = get(v);

    if (sz[ulead] < sz[vlead]) {
      swap(u, v);
      swap(ulead, vlead);
    }

    st.push(Save(ulead, a[ulead], b[ulead], sz[ulead]));
    st.push(Save(vlead, a[vlead], b[vlead], sz[vlead]));

    if (ulead == vlead) {
      b[ulead] = -1;
      return;
    }

    int &utail = b[ulead], &vtail = b[vlead];
    if (utail == -1 || (u != ulead && u != utail) || (v != vlead && v != vtail)) {
      utail = -1;
    } else {
      utail = vtail;
    }
    sz[ulead] += sz[vlead];
    a[vlead] = ulead;
  }

  void rb() {
    assert(!st.empty());
    Save s = st.top(); st.pop();
    a[s.idx] = s.a;
    b[s.idx] = s.b;
    sz[s.idx] = s.sz;
  }

  void rollback() {
    rb();
    rb();
  }
};

const int K = 450;
const int MAXW = 200001;

vector<int> weights;
vector<Edge> t[MAXW];
DSU saves[K];

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  vector<Edge> edges;
  for (int i = 0; i < M; i++) {
    edges.push_back(Edge(U[i], V[i], W[i]));
    weights.push_back(W[i]);
  }
  sort(weights.begin(), weights.end());
  weights.erase(unique(weights.begin(), weights.end()), weights.end());
  for (Edge &e : edges) {
    e.w = lower_bound(weights.begin(), weights.end(), e.w)-weights.begin();
    t[e.w].push_back(e);
  }

  DSU dsu(N);
  for (int w = 0; w < MAXW; w++) {
    for (Edge e : t[w]) {
      dsu.unio(e.u, e.v);
    }

    if (w % K == 0) {
      saves[w / K] = DSU(dsu);
    }
  }
  cerr << "Init finished!" << endl;
}

int getMinimumFuelCapacity(int X, int Y) {

  int block = K;
  for (int i = 0; i < K && i*K < MAXW; i++) {
    if (!saves[i].init) {
      break;
    }
    if (saves[i].get(X) == saves[i].get(Y)) {
      int lead = saves[i].get(X);
      int tail = saves[i].b[lead];
      block = i;
      if (tail == -1) {
        break;
      }
    }
  }
  block--;

  DSU &dsu = saves[block];
  int cnt = 0, ans = -1;
  for (int i = 1; i < K; i++) {
    int w = block * K + i;

    for (Edge e : t[w]) {
      dsu.unio(e.u, e.v);
      cnt++;
    }

    if (dsu.get(X) == dsu.get(Y)) {
      int lead = dsu.get(X);
      int tail = dsu.b[lead];
      if (tail == -1) {
        ans = weights[w];
        break;
      }
    }
  }

  for (int i = 0; i < cnt; i++) {
    dsu.rollback();
  }

  return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Incorrect 7 ms 7648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Execution timed out 2050 ms 517768 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Incorrect 7 ms 7648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Incorrect 7 ms 7648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Incorrect 7 ms 7648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5340 KB Output is correct
2 Correct 4 ms 5344 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Incorrect 7 ms 7648 KB Output isn't correct
5 Halted 0 ms 0 KB -