Submission #446718

#	Time	Username	Problem	Language	Result	Execution time	Memory
446718		prvocislo	Joker (BOI20_joker)	C++17	100 / 100	732 ms	13364 KiB

Joker

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 2e5 + 5, maxvr = maxn * 2;
//const int maxn = 10, maxvr = maxn * 2;
int p[maxvr], siz[maxvr], u[maxn], v[maxn], first[maxn], n, m, q;
vector<int> ch;
int root(int a) { return p[a] == a ? a : root(p[a]); }
void merge(int a, int b)
{
    a = root(a), b = root(b);
    if (a == b) return;
    if (siz[a] < siz[b]) swap(a, b);
    siz[a] += siz[b], p[b] = a;
    ch.push_back(b);
}
void undo(int until)
{
    while (ch.size() > until)
    {
        siz[p[ch.back()]] -= siz[ch.back()];
        p[ch.back()] = ch.back();
        ch.pop_back();
    }
}
bool add(int i)
{
    merge(u[i], v[i]+n), merge(u[i]+n, v[i]);
    return root(v[i]) == root(v[i]+n) || root(u[i]) == root(u[i]+n);
}
void divide_and_conquer(int l1, int l2, int r1, int r2, bool odd) // v dsu mame hrany [0,...,l1-1], [r2,...,m+1]
{
    if (l1 > l2) return;
    int mid = (l1 + l2) >> 1, siz = ch.size();
    bool odd2 = odd;
    for (int i = l1; i < mid; i++) odd2 |= add(i);
    if (odd2) first[mid] = r2;
    else for (int i = r2-1; i >= -1; i--)
    {
        if (i >= 0) odd2 |= add(i);
        if (i != -1 && odd2)
        {
            first[mid] = i;
            break;
        }
    }
    undo(siz);
    odd2 = odd;
    for (int i = r2-1; i >= first[mid]; i--) odd2 |= add(i);
    divide_and_conquer(l1, mid-1, r1, first[mid], odd2);
    undo(siz);
    odd2 = odd;
    for (int i = l1; i <= mid; i++) odd2 |= add(i);
    divide_and_conquer(mid+1, l2, first[mid], r2, odd2);
    undo(siz);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < 2*n; i++) p[i] = i, siz[i] = 1;
    for (int i = 0; i < m; i++) cin >> u[i] >> v[i], u[i]--, v[i]--;
    divide_and_conquer(0, m-1, 0, m, false);
    while (q--)
    {
        int l, r;
        cin >> l >> r; l--, r--;
        if (first[l] > r) cout << "YES\n"; // first[l] - ak mame tuto hranu a prvych l-1 a tie za nou tak mame odd cyclus
        else cout << "NO\n";
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void undo(int)':
Joker.cpp:20:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     while (ch.size() > until)
      |            ~~~~~~~~~~^~~~~~~

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