Submission #928631

#	Time	Username	Problem	Language	Result	Execution time	Memory
928631		aykhn	Joker (BOI20_joker)	C++17	100 / 100	330 ms	20928 KiB

Joker

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MXN = 2e5 + 5;

int n, m;
array<int, 2> ed[MXN];
stack<pair<int*, int>> st;
int par[MXN], sz[MXN], col[MXN], ans[MXN];
int bip = 1;

void make(int &x, int y)
{
    st.push({&x, x});
    x = y;
}
void undo(int c)
{
    while (st.size() > c)
    {
        pair<int*, int> x = st.top();
        *x.first = x.second;
        st.pop();
    }
}
pair<int, int> getpar(int x)
{
    if (x == par[x]) return {x, 0};
    pair<int, int> p = getpar(par[x]);
    return {p.first, p.second ^ col[x]};
}
void merge(int x, int y)
{
    pair<int, int> x1 = getpar(x), y1 = getpar(y);
    if (x1.first == y1.first) 
    {
        if (x1.second == y1.second) make(bip, 0);
        return;
    }
    if (sz[x1.first] < sz[y1.first]) swap(x1, y1);
    make(sz[x1.first], sz[x1.first] + sz[y1.first]);
    make(par[y1.first], x1.first);
    make(col[y1.first], y1.second ^ x1.second ^ 1);
}
void solve(int l, int r, int optl, int optr)
{
    if (l > r) return;
    int mid = (l + r) >> 1;
    int prevsz = st.size();
    for (int i = l; i < mid; i++) 
    {
        merge(ed[i][0], ed[i][1]);
    }
    for (int i = optr; i >= optl; i--)
    {
        merge(ed[i][0], ed[i][1]);
        if (!bip) 
        {
            ans[mid] = i;
            break;
        }
    }
    undo(prevsz);
    if (l == r) return;
    for (int i = ans[mid] + 1; i <= optr; i++)
    {
        merge(ed[i][0], ed[i][1]);
    }
    solve(l, mid - 1, optl, ans[mid]);
    undo(prevsz);
    for (int i = l; i <= mid; i++)
    {
        merge(ed[i][0], ed[i][1]);
    }
    solve(mid + 1, r, ans[mid], optr);
    undo(prevsz);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int q;
    cin >> n >> m >> q;
    for (int i = 0; i <= n; i++) par[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; i++)
    {
        cin >> ed[i][0] >> ed[i][1];
    }
    ed[m + 1] = {0, 1};
    solve(1, m, 1, m + 1);
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        if (ans[l] > r) cout << "YES\n";
        else cout << "NO\n";
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void undo(int)':
Joker.cpp:21:22: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |     while (st.size() > c)
      |            ~~~~~~~~~~^~~

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