oj.uz

답안 #750731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750731 2023-05-30T08:30:16 Z GrindMachine Joker (BOI20_joker) C++17
25 / 100
 474 ms 27572 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
some submissions

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct DSU {
    vector<int> par, rankk;
    vector<int> weight;
    bool is_bip;
    vector<array<int,5>> history;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        weight = vector<int>(n + 1);
        is_bip = true;
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        weight[u] = 0;
    }

    pii find(int u) {
        if (u == par[u]) return {u,0};
        auto [p, cp] = find(par[u]);
        return {p, cp ^ weight[u]};        
    }

    bool same(int u, int v) {
        return find(u).ff == find(v).ff;
    }

    void merge(int u, int v) {
        auto [pu,cu] = find(u);
        auto [pv,cv] = find(v);

        history.pb({pu, par[pu], rankk[pu], weight[pu], is_bip});
        history.pb({pv, par[pv], rankk[pv], weight[pv], is_bip});

        if(pu == pv){
            if(cu == cv){
                is_bip = false;
            }

            return;
        }

        int w = cu ^ cv ^ 1;
        u = pu, v = pv;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        weight[v] = w;
    }

    void rollback(int times){
        times *= 2;
        rep(t,times){
            auto [u,pu,rnk,w,bip] = history.back();
            history.pop_back();

            par[u] = pu;
            rankk[u] = rnk;
            weight[u] = w;
            is_bip = bip;
        }
    }
};

vector<pii> edges(N);
DSU dsu(N);
vector<int> best(N);

void go(int l1, int r1, int l2, int r2){
    if(l1 > r1) return;

    int mid = (l1 + r1) >> 1;
    int opt_mid = r2;
    int cnt = 0;

    for(int i = l1; i < mid; ++i){
        auto [u,v] = edges[i];
        dsu.merge(u,v);
        cnt++;
    }

    rev(i,r2,l2){
        auto [u,v] = edges[i];
        dsu.merge(u,v);
        cnt++;

        if(dsu.is_bip){
            opt_mid = i - 1;
        }
        else{
            break;
        }
    }

    best[mid] = opt_mid;
    dsu.rollback(cnt);

    // add everybody > opt_mid
    cnt = 0;
    for(int i = opt_mid + 1; i <= r2; ++i){
        auto [u,v] = edges[i];
        dsu.merge(u,v);
        cnt++;
    }

    go(l1,mid-1,l2,opt_mid);
    dsu.rollback(cnt);

    // add everybody < mid+1
    cnt = 0;
    for(int i = l1; i <= mid; ++i){
        auto [u,v] = edges[i];
        dsu.merge(u,v);
        cnt++;
    }

    go(mid+1,r1,opt_mid,r2);
    dsu.rollback(cnt);
}

void solve(int test_case)
{
    int n,m,q; cin >> n >> m >> q;
    rep1(i,m) cin >> edges[i].ff >> edges[i].ss;

    go(1,m,1,m);

    assert(dsu.history.empty());

    // rep1(l,n){
    //     cout << best[l] << " ";
    // }
    // cout << endl;

    while(q--){
        int l,r; cin >> l >> r;
        if(r < best[l]){
            yes;
        }
        else{
            no;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 288 ms 15420 KB Output is correct
4 Correct 474 ms 27572 KB Output is correct
5 Correct 266 ms 17144 KB Output is correct
6 Correct 337 ms 17056 KB Output is correct
7 Correct 301 ms 17072 KB Output is correct
8 Correct 316 ms 17204 KB Output is correct
9 Correct 320 ms 17284 KB Output is correct
10 Correct 413 ms 17168 KB Output is correct
11 Correct 338 ms 17272 KB Output is correct
12 Correct 359 ms 17584 KB Output is correct
13 Correct 276 ms 16984 KB Output is correct
14 Correct 307 ms 17140 KB Output is correct
15 Correct 403 ms 17300 KB Output is correct
16 Correct 385 ms 17152 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -