Submission #556884

#	Time	Username	Problem	Language	Result	Execution time	Memory
556884		RaresFelix	Joker (BOI20_joker)	C++17	0 / 100	622 ms	262144 KiB

Joker

#include <bits/stdc++.h>
#define MN 200071
#define MB 149


using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

int n, m, q, bucket_size, R[MN];
pii E[MN];

namespace DSU {
    int PS[MB][MN];
    int BadTime[MB]; /// cand s-a stricat prima data

    inline void init(int id) {
        for(int i = 1; i <= n; ++i) PS[id][i] = -1;
    }

    inline int dist(int id, int u) {
        int re = 0;
        while(PS[id][u] > 0) ++re, u = PS[id][u]; 
        return re;
    }

    inline int repr(int id ,int u) {
        while(PS[id][u] > 0) u = PS[id][u]; 
        return u;
    }
    stack<pii> st[MB];

    inline int time(int id) {
        return st[id].size();
    }

    void uni(int id, int u, int v) {
        int pu = repr(id, u), pv = repr(id, v);
        //printf("    Am primit o operatie de uni pt %d intre %d si %d cu parintii %d si %d\n", id, u, v, pu, pv);
        if(pu == pv) {
            if((dist(id, u) + dist(id, v) + 1) & 1) {
                //printf("   Pt comp %d, la unirea intre %d si %d s-a constatat o problema(dist de %d si %d)\n", id, u, v, dist(id, u), dist(id, v));
                st[id].push({-1, -1}); ///placeholder
                if(!BadTime[id]) BadTime[id] = time(id);
            }
            return;
        }
        if(PS[id][pu] > PS[id][pv]) swap(pu, pv);
        st[id].push({pv, PS[id][pv]});
        PS[id][pu] += PS[id][pv];
        PS[id][pv] = pu;
    }

    void rollback(int id, int tmr) {
        for(int i = time(id); i > tmr; --i) {
            assert(i == time(id));
            if(st[id].top().first != -1)
                PS[id][st[id].top().first] = st[id].top().second;
            st[id].pop();
        }
        //printf("Dupa un rollback la %d de lung %d comp are BT %d\n", id, tmr, BadTime[id]);
        if(BadTime[id] > time(id)) BadTime[id] = 0;
    }
    inline bool okay(int id) {
        if(BadTime[id])
            assert(time(id) >= BadTime[id]);
        return !BadTime[id];
    }
}
int nr_buckets, St[MB], Dr[MB], Bkt[MN];

void add(int poz) {
    //printf("Add pt %d\n", poz);
    for(int i = 1; i <= nr_buckets; ++i) {
        DSU::uni(i, E[poz].first, E[poz].second);
    }
}

int query(int dr) {
    int id = Bkt[dr], tmr0 = DSU::time(id); ///POTI OPTIMIZA PT QUERY-uri LIMITA
    //printf("Query pt poz %d la bucket-ul %d\n", dr, id);
    if(!DSU::okay(id)) return 0;
    for(int i = Dr[id]; i > dr; --i) {
        DSU::uni(id, E[i].first, E[i].second);
    }
    int re = DSU::okay(id);
    DSU::rollback(id, tmr0);
    assert(DSU::okay(id));
    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i)
        cin >> E[i].first >> E[i].second;
    if(m > 4) 
        bucket_size = lround(sqrt(double(m) / log2(double(m))));
    else bucket_size = m;
    //printf("The bucket size is %d\n", bucket_size);
    vector<tuple<int, int, int> > Queries;
    for(int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        Queries.push_back({l, r, i});
    }
    int ld = 0;
    while(ld != m) {
        St[++nr_buckets] = ld + 1;
        ld = Dr[nr_buckets] = min(m, ld + bucket_size);
        for(int i = St[nr_buckets]; i <= Dr[nr_buckets]; ++i) Bkt[i] = nr_buckets;
        //printf("Bucket %d intre %d si %d\n", nr_buckets, St[nr_buckets], ld);
        DSU::init(nr_buckets);
        for(int i = Dr[nr_buckets] + 1; i <= m; ++i) DSU::uni(nr_buckets, E[i].first, E[i].second);
    }
    sort(Queries.begin(), Queries.end());
    int qptr = 0;
    for(int i = 1; i <= m; ++i) {
        while(qptr < int(Queries.size()) && get<0>(Queries[qptr]) == i) {
            R[get<2>(Queries[qptr])] = query(get<1>(Queries[qptr]));
            ++qptr;
        }
        add(i);
    }
    assert(qptr == q);
    for(int i = 1; i <= q; ++i) {
        cout << (!R[i] ? "YES\n" : "NO\n");
    }
    return 0;
}

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