Submission #255070

#	Time	Username	Problem	Language	Result	Execution time	Memory
255070		davitmarg	Joker (BOI20_joker)	C++17	100 / 100	390 ms	9956 KiB

Joker

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

int p[N],col[N],BI,sz[N];
vector<pair<pair<int, int>, int>>st;

void init(int n)
{
    st.clear();
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        col[i] = 0;
        sz[i] = 1;
    }
}

void und()
{
    int b = st.back().first.first;
    int a = st.back().first.second;
    if (a == b)
    {
        BI -= st.back().second;
        st.pop_back();
        return;
    }
    sz[a] -= st.back().second;
    sz[b] += st.back().second;
    p[b] = b;
    st.pop_back();
}

pair<int, int> get(int v)
{
    int c=col[v];
    while (v != p[v])
    {
        v = p[v];
        c ^= col[v];
    }
    return MP(v, c);
}

void dsu(int a, int b)
{
    pair<int,int> A = get(a), B = get(b);
    if (A.first == B.first)
    {
        if (A.second == B.second)
            BI++;
        st.push_back(MP(MP(A.first, B.first), (A.second == B.second)));
        return;
    }
    if (sz[A.first] < sz[B.first])
        swap(A, B);
    st.push_back(MP(MP(B.first, A.first), sz[B.first]));
    if (A.second == B.second)
        col[B.first] ^= 1;

    sz[A.first] += sz[B.first];
    sz[B.first] = 0;
    p[B.first] = A.first;
    col[B.first] ^= col[A.first];
}


int n, m, q, L[N], R[N],X[N],Y[N], used[N], d[N], fnd, pos[N];

void solve(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    int m = (l + r) / 2;
    for (int i = l; i < m; i++)
        dsu(X[i], Y[i]);
    int optm = optr + 1;
    for (int i = optr; i >= m && i>=optl && BI==0; i--)
    {
        dsu(X[i], Y[i]);
        if (BI || i == m)
        {
            optm = i;
            und();
            break;
        }
    }
    pos[m] = optm;
    optm = min(optr, optm);
    
    for (int i = optr; i > optm; i--)
        und();
    for (int i = l; i < m; i++)
        und();

    for (int i = optr; i > optm; i--)
        dsu(X[i], Y[i]);

    solve(l, m - 1, optl, optm);

    for (int i = optr; i > optm; i--)
        und();

    for (int i = l; i <= m; i++)
        dsu(X[i], Y[i]);
    solve(m + 1, r, max(optm, m + 1), optr);
    for (int i = l; i <= m; i++)
        und();
}

int main()
{
    fastIO;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
        cin >> X[i] >> Y[i];

    init(n);

    solve(1, m, 1, m);

    for (int i = 1; i <= q; i++)
    {
        cin >> L[i] >> R[i];
        if (R[i] >= pos[L[i]])
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

/*




*/

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