Submission #1073373

#TimeUsernameProblemLanguageResultExecution timeMemory
1073373beaconmcPictionary (COCI18_pictionary)C++17
0 / 140
495 ms63744 KiB
#include <bits/stdc++.h> typedef long long ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) using namespace std; const ll maxn = 100005; set<vector<ll>> req[maxn]; set<ll> has[maxn]; map<ll,ll> opps; ll cmp[maxn]; ll find(ll a){ while (a != cmp[a]){ cmp[a] = cmp[cmp[a]]; a = cmp[a]; } return a; } map<vector<ll>, ll> ans; void unite(ll a, ll b, ll k){ if (find(a) == find(b)) return; ll A = find(a); ll B = find(b); if (req[B].size() > req[A].size()){ swap(A, B); } vector<vector<ll>> used; for (auto&i : req[B]){ if (has[A].count(i[0])){ ans[{i[0], i[1]}] = k; used.push_back(i); } } for (auto&i : used) req[B].erase(i); for (auto&i : used) reverse(i.begin(), i.end()); for (auto&i : used) req[A].erase(i); if (has[A].size() > has[B].size()) swap(has[A], has[B]); for (auto&i : has[A]){ has[B].insert(i); } if (req[A].size() > req[B].size()) swap(req[A], req[B]); for (auto&i : req[A]){ req[B].insert(i); } cmp[A] = B; } int main(){ FOR(i,0,maxn) cmp[i] = i; ll n,m,q; cin >> n >> m >> q; vector<vector<ll>> queries; FOR(i,0,q){ ll a,b; cin >> a >> b; queries.push_back({a,b}); req[b].insert({a, b}); req[a].insert({b,a}); } FOR(i,1,n+1) has[i].insert(i); FORNEG(i, m, 0){ ll cur = i; while (cur+i < n){ unite(cur, cur+i, i); cur+=i; } } for (auto&i : queries){ if (ans.count(i)) cout << m-ans[i]+1 << "\n"; else{ reverse(i.begin(), i.end()); cout << m-ans[i]+1 << "\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...