제출 #1085956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085956		not_amir	Joker (BOI20_joker)	C++14	100 / 100	165 ms	11092 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define pib pair<int, bool>
 
struct weightedDSU{
    vector<int> parent, weight, index;
    vector<bool> val;
    
    weightedDSU(int n) : parent(n), weight(n, -1), index(n), val(n) {
        for(int i = 0; i < n; i++){
            parent[i] = i;
            index[i] = rand();
        }
    }
    
    pib getRoot(int v, int w = 0){
        bool x = 0;
        while(weight[v] >= w){
            while(weight[parent[v]] >= weight[v]){
                val[v] = val[v] ^ val[parent[v]];
                parent[v] = parent[parent[v]];
            }
            x ^= val[v];
            v = parent[v];
        }
        return {v, x};
    }
    
    void addEdgeHelper(int u, int v, int w, bool x){
        while(u != v){
            pib tmp;
            tmp = getRoot(u, w);
            x ^= tmp.second;
            u = tmp.first;
            tmp = getRoot(v, w);
            x ^= tmp.second;
            v = tmp.first;
            if(index[u] < index[v])
                swap(u, v);
            int temp_parent = parent[v], temp_weight = weight[v];
            bool temp_val = val[v];
            parent[v] = u;
            weight[v] = w;
            val[v] = x;
            u = temp_parent;
            w = temp_weight;
            x = temp_val;
        }
    }
    
    int mainEdge(int u, int v){
        while(u != parent[v] && v != parent[u]){
            if(weight[u] > weight[v])
                u = parent[u];
            else
                v = parent[v];
        }
        if(u == parent[v])
            return v;
        else
            return u;
    }
    
    void deleteEdge(int u, int v, int w){
        getRoot(u);
        getRoot(v);
        int p = mainEdge(u, v);
        if(weight[p] == w){
            parent[p] = p;
            weight[p] = -1;
        }
    }
};
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    weightedDSU mst(n + 1);
    vector<pii> edges(m);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
    }
    int curr = 0;
    vector<int> last(m + 1);
    for(int k = 0; k < 2 * m; k++){
        int i = k % m;
        int u = edges[i].first, v = edges[i].second;
        pib u1 = mst.getRoot(u), v1 = mst.getRoot(v);
        if(u1.first == v1.first){
            int p = mst.mainEdge(u, v);
            if(u1.second == v1.second){
                int e = mst.weight[p];
                for(; curr <= e; curr++)
                    mst.deleteEdge(edges[curr % m].first, edges[curr % m].second, curr);
            }
            else{
                mst.parent[p] = p;
                mst.weight[p] = -1;
            }
        }
        mst.addEdgeHelper(u, v, k, 1);
        if(k > m - 2)
            last[k - m + 1] = curr;
    }
    while(q--){
        int l, r;
        cin >> l >> r;
        if(r < last[l - 1])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

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