Submission #973874

#	Time	Username	Problem	Language	Result	Execution time	Memory
973874		ttttttttttttth	Joker (BOI20_joker)	C++17	100 / 100	272 ms	19516 KiB

Joker

// Author: Ivan Teo
// Created: Thu May 02 18:44:14 2024

#define TASKNAME "joker"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

const int N = 2e5 + 5;
stack<int> ev;
int n, m, q, u[N], v[N], p[N << 1], sz[N << 1], ans[N];
bool odd;

int get(int x)
{
    while (x != p[x]) x = p[x];
    return x;
}

void uni(int u, int v)
{
    u = get(u);
    v = get(v);
    if (u == v) return ;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    p[v] = u;
    ev.push(v);
}

void roll(int x)
{
    while (sz(ev) > x)
    {
        int u = ev.top();
        ev.pop();
        if (u == -1) odd = 0;
        else sz[p[u]] -= sz[u], p[u] = u;
    }
}

void add(int a, int b)
{
    uni(a, b + n), uni(b, a + n);
    if (!odd) if (get(a) == get(a + n) || get(b) == get(b + n))
            odd = 1, ev.push(-1);
}

void dac(int l, int r, int opl, int opr)
{
    if (l > r) return ;
    int mid = l + r >> 1, snap = sz(ev);
    fore(i, l, mid - 1) add(u[i], v[i]);
    int ri = sz(ev);
    ans[mid] = -1;
    for (int i = opr; i >= max(mid, opl); i--)
    {
        if (odd)
        {
            ans[mid] = i;
            break;
        }
        add(u[i], v[i]);
    }
    if (ans[mid] == -1) ans[mid] = mid - 1;
    roll(ri);
    add(u[mid], v[mid]);
    dac(mid + 1, r, ans[mid], opr);
    roll(snap);
    for (int i = opr; i > ans[mid]; i--) add(u[i], v[i]);
    dac(l, mid - 1, opl, ans[mid]);
    roll(snap);
}

void solve()
{
    iota(p, p + (N << 1), 0);
    fill(sz, sz + (N << 1), 1);
    cin >> n >> m >> q;
    fore(i, 1, m) cin >> u[i] >> v[i];
    dac(1, m, 1, m); 
    while (q--)
    {
        int a, b; cin >> a >> b;
        cout <<  (b <= ans[a] ? "YES\n" : "NO\n");
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
        freopen(TASKNAME ".inp", "r", stdin),
                freopen(TASKNAME ".out", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void dac(long long int, long long int, long long int, long long int)':
Joker.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = l + r >> 1, snap = sz(ev);
      |               ~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
Joker.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TASKNAME ".inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:114:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |                 freopen(TASKNAME ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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