제출 #1166590

#제출 시각아이디문제언어결과실행 시간메모리
1166590black_thirdPictionary (COCI18_pictionary)C++20
140 / 140
141 ms15244 KiB
#include <iostream> #include <sstream> #include <set> #include <fstream> #include <algorithm> #include <cctype> #include <iomanip> #include <vector> #include <map> #include <queue> #include <numeric> #include <string> #include <cmath> #include <climits> #include <stack> #include <complex> #include <cstdlib> #include <cstring> #include <array> #include <unordered_map> #include <unordered_set> #include <functional> #include <bitset> #include <cassert> #include <tuple> using namespace std; typedef long long ll; typedef long double ld; //const int mod = 998244353; const int mod = 1e9+7; const int N=5e5+5; struct DSU { vector<int> par, sz; DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); } int find(int x) { if(x == par[x])return x; return par[x] = find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } bool join(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; par[y] = x; return true; } int size(int x) { return sz[find(x)]; } }; void solve() { int n,m,q; cin>>n>>m>>q; vector <vector<int>> div(m+1); for (int i=1;i<=m;i++) { for (int j=2*i;j<=n;j+=i) div[i].push_back(j); } vector <pair<int,int>> quer; quer.push_back({0,0}); for (int i=1;i<=q;i++) { int a,b; cin>>a>>b; quer.push_back({a,b}); } vector <int> qe(q+1,m),qs(q+1,1); bool lessa=true; while (lessa) { lessa=false; vector <vector<int>> mids(m+1); DSU dsu(n+1); for (int i=1;i<=q;i++) { if (qe[i]>=qs[i]) { mids[(qe[i]+qs[i])>>1].push_back(i); lessa=true; } } for (int mid=1;mid<=m;mid++) { for (auto i : div[m-mid+1]) { dsu.join(m-mid+1,i); } for (auto j : mids[mid]) { if (dsu.same(quer[j].first,quer[j].second)) { qe[j]=mid-1; } else { qs[j]=mid+1; } } } } for (int i=1;i<=q;i++) { if (qe[i]==m) cout<<"-1\n"; else cout<<qe[i]+1<<'\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t=1; //cin>>t; while (t--) { solve(); } return 0; }
#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...