Submission #556882

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

Joker

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


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) {
            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) {
        return !BadTime[id] || time(id) < 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);
    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);
    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 < Queries.size() && get<0>(Queries[qptr]) == i) {
            R[get<2>(Queries[qptr])] = query(get<1>(Queries[qptr]));
            ++qptr;
        }
        add(i);
    }
    for(int i = 1; i <= q; ++i) {
        cout << (!R[i] ? "YES\n" : "NO\n");
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while(qptr < Queries.size() && get<0>(Queries[qptr]) == i) {
      |               ~~~~~^~~~~~~~~~~~~~~~

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