제출 #1183036

#제출 시각아이디문제언어결과실행 시간메모리
1183036AMnuPictionary (COCI18_pictionary)C++20
140 / 140
84 ms23812 KiB
#include <bits/stdc++.h> #define fi first #define se second #define bupo __builtin_popcount using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MAXN = 2e5+5; int N, M, Q, A[MAXN], B[MAXN]; int P, L[MAXN], R[MAXN], ans[MAXN], par[MAXN]; vector <int> mid[MAXN]; vector <pii> edge[MAXN]; int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); } void join(int x,int y) { x = find(x); y = find(y); par[x] = y; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M >> Q; for (int i=1;i<=N;i++) { par[i] = i; } for (int i=M;i>1;i--) { for (int j=2*i;j<=N;j+=i) { if (find(i) != find(j)) { join(i,j); edge[M+1-i].push_back({i,j}); } } } for (int i=1;i<=Q;i++) { cin >> A[i] >> B[i]; L[i] = 1; R[i] = M-1; ans[i] = M; if (L[i] <= R[i]) { mid[(L[i]+R[i])/2].push_back(i); } else { P++; } } while (P < Q) { for (int i=1;i<=N;i++) { par[i] = i; } for (int i=1;i<M;i++) { for (pii x : edge[i]) { join(x.fi,x.se); } for (int j : mid[i]) { if (find(A[j]) == find(B[j])) { ans[j] = i; R[j] = i - 1; } else { L[j] = i + 1; } if (L[j] <= R[j]) { mid[(L[j]+R[j])/2].push_back(j); } else { P++; } } mid[i].clear(); } } for (int i=1;i<=Q;i++) { cout << ans[i] << "\n"; } }
#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...