Submission #1100285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100285		MateiKing80	Joker (BOI20_joker)	C++14	100 / 100	1029 ms	25272 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU
{
    int path[400400], rnk[400400];
    vector<array<int, 3>> st;

    void init(int n)
    {
        st.clear();
        for(int i = 1; i <= n; i ++)
            path[i] = i, rnk[i] = 0;
    }
    int realpapa(int s)
    {
        if(s == path[s])
            return s;
        return realpapa(path[s]);
    }
    void unite(int x, int y)
    {
        x = realpapa(x), y = realpapa(y);
        if(x == y)
        {
            st.push_back({-1, -1, -1});
            return;
        }
        if(rnk[x] > rnk[y])
            swap(x, y);
        st.push_back({x, y, rnk[y]});
        path[x] = y;
        if(rnk[x] == rnk[y])
            rnk[y] ++;
    }
    void pop(int cnt)
    {
        for(int i = 1; i <= cnt; i ++)
        {
            auto [x, y, r] = st.back();
            st.pop_back();
            if(x == -1)
                continue;
            path[x] = x;
            rnk[y] = r;
        }
    }
} dsu;

int a[400400], b[400400], ans[400400], sz;

void rollback(int t)
{
    dsu.pop((sz - t) * 2);
    sz = t;
}

int push(int i)
{
    dsu.unite(a[i] * 2, b[i] * 2 + 1);
    dsu.unite(a[i] * 2 + 1, b[i] * 2);
    sz ++;
    if(dsu.realpapa(a[i] * 2) == dsu.realpapa(a[i] * 2 + 1))
        return 0;
    return 1;
}

void solve(int l, int r, int s, int e)
{
    if(l > r)
        return;
    int m = (l + r) >> 1;
    int t1 = sz;
    for(int i = min(r, s - 1); i >= m; i --)
        push(i);
    int t2 = sz;
    for(int i = max(s, m); i <= e; i ++)
    {
        if(!push(i))
            break;
        ans[m] = i;
    }
    rollback(t2);
    solve(l, m - 1, s, ans[m]);
    rollback(t1);
    for(int i = max(r + 1, s); i <= ans[m] - 1; i ++)
        push(i);
    solve(m + 1, r, ans[m], e);
    rollback(t1);
}

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i ++)
        cin >> a[i] >> b[i];
    for(int i = 1; i <= m; i ++)
        a[i + m] = a[i], b[i + m] = b[i];
    dsu.init(n * 2 + 3);
    solve(1, m * 2, 1, m * 2);
    while(q --)
    {
        int l, r;
        cin >> l >> r;
        int ll = r + 1, rr = l - 1 + m;
        if(ans[ll] >= rr)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

Compilation message (stderr)

Joker.cpp: In member function 'void DSU::pop(int)':
Joker.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |             auto [x, y, r] = st.back();
      |                  ^

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