Submission #1304955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304955		vlomaczk	Joker (BOI20_joker)	C++20	0 / 100	0 ms	332 KiB

Joker

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

struct DSU {
    vector<int> parent, size, color;
    bool bipartite;
    stack<tuple<int,int,int,int>> history; // a, parent[a], size[a], color[a]

    DSU(int n) {
        parent.resize(n);
        size.assign(n,1);
        color.assign(n,-1);
        bipartite = true;
        for(int i=0;i<n;i++) parent[i]=i;
    }

    int find(int x) {
        return parent[x]==x ? x : find(parent[x]);
    }

    void unite(int x, int y) {
        int px = find(x), py = find(y);
        int cx = color[x], cy = color[y];

        if(px==py) {
            if(cx==cy) bipartite=false; // pojawił się cykl nieparzysty
            return;
        }

        if(size[px] < size[py]) swap(px,py);

        // zapis do rollback
        history.push({py,parent[py],size[px],color[py]});

        parent[py] = px;
        size[px] += size[py];

        // ustaw kolor dla spójności bipartite
        if(cx==-1 && cy==-1) {
            color[x] = 0;
            color[y] = 1;
        } else if(cx==-1) color[x] = 1-cy;
        else if(cy==-1) color[y] = 1-cx;
    }

    void rollback() {
        if(history.empty()) return;
        auto [py, prev_parent, prev_size, prev_color] = history.top(); history.pop();
        size[parent[py]] = prev_size;
        parent[py] = prev_parent;
        color[py] = prev_color;
        bipartite = true; // resetujemy, bo i tak liczymy tylko raz dla l=1
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,q;
    cin >> n >> m >> q;
    vector<pair<int,int>> edges(m);
    for(int i=0;i<m;i++){
        int u,v; cin >> u >> v;
        u--; v--; // zero-index
        edges[i] = {u,v};
    }

    // znajdź największy indeks krawędzi, przy którym graf pozostaje dwudzielny
    DSU dsu(n);
    int lim = m; // minimalny numer krawędzi, przy którym graf przestaje być bipartite
    for(int i=0;i<m;i++){
        dsu.unite(edges[i].first, edges[i].second);
        if(!dsu.bipartite){
            lim = i;
            break;
        }
    }

    // dla każdego zapytania
    while(q--){
        int l,r; 
        cin >> l >> r;
        l--; r--;
        // podzadanie l=1, więc l=0
        if(r < lim) cout << "YES\n";
        else cout << "NO\n";
    }
}

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