oj.uz

Submission #93517

# Submission time Handle Problem Language Result Execution time Memory
93517 2019-01-09T09:42:21 Z dfistric Pictionary (COCI18_pictionary) C++14
140 / 140
 413 ms 15860 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;

using namespace std;

const int MAXN = 1e5 + 10;
int lo[MAXN], hi[MAXN];
vector <int> mi[MAXN];
int a[MAXN], b[MAXN];
int par[MAXN];

int nadi(int x) {
  if (x != par[x]) par[x] = nadi(par[x]);
  return par[x];
}

void spoji(int x, int y) {
  x = nadi(x);
  y = nadi(y);
  par[y] = x;
  return;
}

int main() {
  ios_base::sync_with_stdio(false);

  int n, m, q;
  cin >> n >> m >> q;

  REP(i, q) {
    cin >> a[i] >> b[i];
    lo[i] = 1;
    hi[i] = m;
  }

  REP(bi, 20) {
    REP(i, n + 1) par[i] = i;

    REP(i, q) {
      int mid = (lo[i] + hi[i]) / 2;
      mi[mid].push_back(i);
    }

    FORd(k, m, 1) {
      int st = k + k;
      while (st <= n) {
        spoji(k, st);
        st += k;
      }

      int p = m - k + 1;
      for (int ne : mi[p]) {
        if (nadi(a[ne]) == nadi(b[ne])) {
          hi[ne] = p;
        } else {
          lo[ne] = p + 1;
        }
      }
      mi[p].clear();
    }
  }

  REP(i, q) cout << lo[i] << "\n";

  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3960 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7456 KB Output is correct
2 Correct 47 ms 6616 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9416 KB Output is correct
2 Correct 60 ms 8400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7792 KB Output is correct
2 Correct 93 ms 7356 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 8208 KB Output is correct
2 Correct 105 ms 7160 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 10620 KB Output is correct
2 Correct 168 ms 7992 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 8688 KB Output is correct
2 Correct 282 ms 11856 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 13748 KB Output is correct
2 Correct 360 ms 12656 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 15860 KB Output is correct
2 Correct 413 ms 14196 KB Output is correct