oj.uz

Submission #1076504

# Submission time Handle Problem Language Result Execution time Memory
1076504 2024-08-26T14:22:49 Z fryingduc Pictionary (COCI18_pictionary) C++17
140 / 140
 230 ms 20656 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

const int maxn = 1e5 + 5;
int n, m, q;
vector<int> g[maxn];
pair<int, int> que[maxn];
int ans[maxn];
int le[maxn], ri[maxn];
vector<int> cand[maxn];


struct dsu {
  int n;
  vector<int> par;
  dsu() {}
  dsu(int n) : n(n), par(n + 5) {
    for(int i = 1; i <= n; ++i) par[i] = i;
  }
  int find(int u) {
    return u == par[u] ? u : par[u] = find(par[u]);
  }
  void join(int u, int v) {
    u = find(u), v = find(v);
    if(u == v) return;
    par[v] = u;
  }
} d;
void solve() {
  cin >> n >> m >> q;
  for(int i = 1; i <= q; ++i) {
    cin >> que[i].first >> que[i].second;
    le[i] = 1, ri[i] = m;
    ans[i] = -1;
  }
  while(1) {
    bool exist = 0;
    for(int i = 1; i <= q; ++i) {
      if(le[i] <= ri[i]) {
        int mid = (le[i] + ri[i]) >> 1;
        cand[mid].push_back(i);
        exist = 1;
      }
    }
    if(!exist) break;

    d = dsu(n + m);
    for(int mid = 1; mid <= m; ++mid) {
      int x = m - mid + 1;
      for(int j = x; j <= n; j += x) {
        d.join(j, x + n);
      }
      for(auto i:cand[mid]) {
        bool flag = d.find(que[i].first) == d.find(que[i].second);
        if(flag) {
          ans[i] = mid;
          ri[i] = mid - 1;
        }
        else le[i] = mid + 1;
      }
      cand[mid].clear();
    }
  }

  for(int i = 1; i <= q; ++i) {
    cout << ans[i] << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6236 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9956 KB Output is correct
2 Correct 20 ms 9180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12200 KB Output is correct
2 Correct 28 ms 11040 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10296 KB Output is correct
2 Correct 49 ms 10036 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 11076 KB Output is correct
2 Correct 56 ms 10016 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 13964 KB Output is correct
2 Correct 86 ms 11312 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 11728 KB Output is correct
2 Correct 141 ms 15304 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 17528 KB Output is correct
2 Correct 164 ms 16176 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 20656 KB Output is correct
2 Correct 212 ms 17796 KB Output is correct