Submission #1076504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076504		fryingduc	Pictionary (COCI18_pictionary)	C++17	140 / 140	230 ms	20656 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14