Submission #765468

#	Time	Username	Problem	Language	Result	Execution time	Memory
765468		canadavid1	Joker (BOI20_joker)	C++17	0 / 100	165 ms	8300 KiB

Joker

#include <bits/stdc++.h>
#include <linux/limits.h>

using namespace std;

struct Query {
    int id;
    int l,r;
    Query(){};
    const bool operator<(Query& other) const 
    {
        //if (l/512 != other.l/512) return l > other.l;
        return r < other.r;
    }
    
};


vector<pair<int,int>> edge;
struct UnionFind
{
    vector<int> parent;
    vector<int> size;
    vector<bool> parity;
    vector<pair<int,int>> history;
    vector<bool> history_valid;
    UnionFind(int N)
    {
        parent.assign(N+1,-1);
        size.assign(N+1,1);
        parity.assign(N+1,0);
        history.assign(1,{-1,-1});
        history_valid.assign(1,1);
    }
    pair<int,bool> find(int a,bool c = false)
    {
        if (parent[a]==-1) return {a,c};
        return find(parent[a],c^parity[a]);
    }
    void unite(int a, int b)
    {
        auto av = find(a);
        auto bv = find(b);
        a = av.first;
        b = bv.first;
        bool apar = av.second;
        bool bpar = av.second;
        if(a==b)
        {
            history.push_back({-1,-1});
            history_valid.push_back(history_valid.back()&&(apar!=bpar));
            return;
        }
        if (size[a] < size[b]) {swap(a,b);swap(apar,bpar);}
        // a > b
        size[a] += size[b];
        parent[b] = a;
        parity[b] = apar == bpar;
        history.push_back({a,b});
        history_valid.push_back(history_valid.back());
    }
    bool isValid()
    {
        return history_valid.back();
    }
    void undo()
    {
        auto ab = history.back();history.pop_back();
        history_valid.pop_back();
        if(ab.first == -1) return;
        auto a = ab.first;
        auto b = ab.second;
        size[a] -= size[b];
        parent[b] = -1;
        parity[b] = 0;
    }
    inline void addEdge(int i)
    {
        unite(edge[i-1].first,edge[i-1].second);
    }
};


int id,l,r,Redge,Lpos,Rpos;
signed main()
{
    int N,M,Q;
    cin >> N >> M >> Q;
    UnionFind unionfind(N);
    edge.resize(M);
    for(auto&& i : edge) cin >> i.first >> i.second;
    vector<Query> query(Q);
    for(auto&& i : query) cin >> i.l>> i.r;
    for(int i = 0; i < Q; i++) query[i].id = i;
    sort(query.begin(),query.end());
    vector<bool> queryres(Q);
    //Redge = N;
    Lpos = 1;
    Rpos = M;
    Redge = M;
    while(query.size())
    {
        auto v = query.back();query.pop_back();
        id = v.id;
        l = v.l;
        r = v.r;
        /* if (l >= Rpos)
        {
            for(int i = N; i > Redge; i--) unionfind.undo();
            for(int i = Lpos; i < Rpos; i++) unionfind.addEdge(i);
            Redge = N;
            Lpos = Rpos;
            Rpos = min(N,Lpos+512);
        } */
        for(;Redge > r; Redge--) unionfind.addEdge(Redge);
        for(int i = Lpos; i < l;i++) unionfind.addEdge(i);
        queryres[id] = unionfind.isValid();
        for(int i = Lpos; i < l;i++) unionfind.undo();
    }
    for(auto i : queryres) cout << (i ? "NO\n" : "YES\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