This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n, m, q;
cin >> n >> m >> q;
vector <pair <ll, ll>> kv(q);
for (int i = 0; i < q; i++)
cin >> kv[i].first >> kv[i].second;
vector <ll> lo(q, 1);
vector <ll> hi(q, m + 1);
vector <ll> rjesenja(q, -1);
ll rjeseni = 0;
while (rjeseni < q){
vector <pair <ll,ll>> mids(q);
for (int i = 0; i < q; i++)
mids[i].first = (lo[i]+hi[i])/2, mids[i].second = i;
sort(mids.begin(), mids.end());
vector <ll> par(n+1);
vector <ll> ranks(n+1);
for (int i = 0; i < n; i++)
par[i+1] = i + 1, ranks[i+1] = 0;
ll slid = 0;
for (int i = 0; i < m; i++){
ll tren = 2*(m - i);
while (tren <= n){
ll part = tren;
while (part != par[part])
part = par[part];
ll pars = m - i;
while (pars != par[pars])
pars = par[pars];
if (pars == part){
tren += m - i;
continue;
}
if (ranks[pars] < ranks[part])
swap(pars,part);
par[part] = pars;
if (ranks[pars] == ranks[part]) ranks[pars]++;
tren += m - i;
}
while (slid <= q && mids[slid].first == i + 1){
ll upit = mids[slid].second;
if (rjesenja[upit] != -1){
slid++;
continue;
}
ll para = kv[upit].first, parb = kv[upit].second;
while (para != par[para])
para = par[para];
while (parb != par[parb])
parb = par[parb];
if (para == parb){
hi[upit] = i + 1;
} else {
lo[upit] = i + 2;
}
if (lo[upit] >= hi[upit])
rjeseni++, rjesenja[upit] = lo[upit];
slid++;
}
}
}
for (int i = 0; i < q; i++)
cout << rjesenja[i] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |