Submission #1032137

#TimeUsernameProblemLanguageResultExecution timeMemory
1032137borisAngelovPictionary (COCI18_pictionary)C++17
126 / 140
108 ms48472 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; int n, m, k; pair<int, int> queries[maxn]; int answers[maxn]; struct DSU { int par[maxn]; int dep[maxn]; void init(int n) { for (int i = 1; i <= n; ++i) { dep[i] = 1; par[i] = i; } } int root(int node) { if (node == par[node]) return node; return par[node] = root(par[node]); } void connect(int x, int y) { x = root(x); y = root(y); if (x == y) return; if (dep[x] < dep[y]) swap(x, y); par[y] = x; if (dep[x] == dep[y]) ++dep[x]; } bool areConnected(int x, int y) { return root(x) == root(y); } }; DSU dsu; vector<int> tree[4 * maxn]; struct ParallelNode { int node; int l; int r; int level; }; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> m >> k; for (int i = 1; i <= k; ++i) { cin >> queries[i].first >> queries[i].second; } for (int i = 1; i <= k; ++i) { tree[1].push_back(i); answers[i] = m; } int prvLevel = -1; int ptrLevel = 0; queue<ParallelNode> q; q.push({1, 1, m, 1}); while (!q.empty()) { ParallelNode curr = q.front(); q.pop(); if (prvLevel != curr.level) { prvLevel = curr.level; dsu.init(n); ptrLevel = 0; } int mid = (curr.l + curr.r) / 2; for (int i = ptrLevel + 1; i <= mid; ++i) { int gcd = m - i + 1; for (int nodeNum = gcd; nodeNum + gcd <= n; nodeNum += gcd) { dsu.connect(nodeNum, nodeNum + gcd); } } ptrLevel = mid; int node = curr.node; for (int i = 0; i < tree[node].size(); ++i) { int idx = tree[node][i]; //cout << mid << " :: " << queries[idx].first << " " << queries[idx].second << " :: " << dsu.areConnected(queries[idx].first, queries[idx].second) << endl; if (dsu.areConnected(queries[idx].first, queries[idx].second) == true) { answers[idx] = min(answers[idx], mid); tree[2 * node].push_back(idx); } else { tree[2 * node + 1].push_back(idx); } } if (curr.l == curr.r) continue; if (!tree[2 * node].empty()) { q.push({2 * node, curr.l, mid, curr.level + 1}); } if (!tree[2 * node + 1].empty()) { q.push({2 * node + 1, mid + 1, curr.r, curr.level + 1}); } } for (int i = 1; i <= k; ++i) { cout << answers[i] << "\n"; } return 0; }

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int i = 0; i < tree[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...