Submission #1049293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049293		windowwife	Joker (BOI20_joker)	C++17	100 / 100	141 ms	14544 KiB

Joker

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 4e5 + 2;
int n, m, q, max_r[maxn], u[maxn], v[maxn], l, r, par[maxn];
vector<pair<int, int>> rb;
int find_set (int u)
{
    if (par[u] < 0) return u;
    return find_set(par[u]);
}
void union_set (int u, int v)
{
    int pu = find_set(u), pv = find_set(v);
    if (pu == pv) return;
    if (par[pu] > par[pv]) swap(pu, pv);
    rb.push_back({pu, par[pu]});
    rb.push_back({pv, par[pv]});
    par[pu] += par[pv];
    par[pv] = pu;
}
void rollback ()
{
    if (rb.empty()) return;
    par[rb.back().first] = rb.back().second;
    rb.pop_back();
}
void pbs (int low, int high, int r)
{
    if (low > high) return;
    //cout << low << " " << high << " " << r << endl;
    int mid = (low + high)/2, tmp = rb.size();
    for (int i = max(low - 1, 1); i < mid; i++)
    {
        //cout << i << endl;
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            for (int j = mid; j <= high; j++) max_r[j] = r;
            while ((int)rb.size() > tmp) rollback();
            pbs(low, mid - 1, r);
            return;
        }
    }
    int tmp2 = rb.size();
    for (int i = r - 1; i >= low; i--)
    {
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            max_r[mid] = i;
            break;
        }
    }
    while ((int)rb.size() > tmp2) rollback();
    pbs(mid + 1, high, r);
    while ((int)rb.size() > tmp) rollback();
    for (int i = r - 1; i >= max(max_r[mid], low); i--)
    {
        union_set(u[i], v[i] + n);
        union_set(u[i] + n, v[i]);
        if (find_set(u[i]) == find_set(u[i] + n))
        {
            for (int j = low; j <= mid; j++) max_r[j] = max_r[mid];
            return;
        }
    }
    pbs(low, mid - 1, max_r[mid]);
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= 2*n; i++) par[i] = -1;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i];
    pbs(1, m, m + 1);
    while (q--)
    {
        cin >> l >> r;
        cout << (r < max_r[l] ? "YES" : "NO") << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29