ABC155 F - Perils in Parallel - ferinの競プロ帳

まず，各ケーブルについて爆弾 $\lbrack l_i,r_i)$ のスイッチを反転するという形に書き換えておきます．

爆弾のスイッチについて差分XORを取っておくと，区間に一様にXORするという操作は2点にXORを行う操作に帰着できます．この操作を繰り返し行ったときに，値を全て0にできるか？という問題になります．適当にスイッチがオフの爆弾を追加しておけば，爆弾が全部オンで差分XORが全て0になる状況は回避できます．

$\lbrack l_i,r_i)$ に作用するスイッチが存在した場合，頂点 $l_i$ と頂点 $r_i$ を結ぶ辺を追加したグラフを考えます．頂点の値は差分XORを取った値に対応させます．このグラフの辺の部分集合をうまく選び，次数の偶奇と頂点の値を一致させることができるか？という問題に帰着できました．

DFS木を葉からボトムアップで参照していきます．辺 $(v,ch)$ について子 $ch$ の頂点の値が1ならば辺を使用する集合に追加し． $v$ の頂点の値を変化させます．この処理を行ったあと，根以外については条件を満たすようになっています．根の値が0ならば，その連結成分については条件を満たす辺集合のとり方が存在します．根の値が1の場合は条件を満たす辺集合が存在しません．なぜなら，辺を追加することで次数の偶奇が変化する頂点は2つであり，1頂点(根だけ)の次数の偶奇を変更しようとしても，次数が一致している頂点の個数の偶奇が合わないからです．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<PII> a(n);  
    REP(i, n) cin >> a[i].first >> a[i].second;  
    a.push_back({INF, 0});  
    sort(ALL(a));  
  
    // XOR差分取っておくと2点に対する更新になる  
    vector<ll> x(n+1);  
    REP(i, n+1) x[i] = a[i].second ^ (i==0 ? 0 : a[i-1].second);  
  
    vector<vector<PII>> g(n+1);  
    REP(i, m) {  
        ll l0, r0;  
        cin >> l0 >> r0;  
        // [l, r) の爆弾に作用する  
        ll l = lower_bound(ALL(a), PII(l0, 0)) - a.begin();  
        ll r = upper_bound(ALL(a), PII(r0, 1)) - a.begin();  
        if(l < r) {  
            g[l].emplace_back(r, i);  
            g[r].emplace_back(l, i);  
        }  
    }  
  
    vector<ll> ans;  
    vector<bool> used(n);  
    function<ll(ll,ll)> dfs = [&](ll v, ll p) {  
        used[v] = true;  
        ll ret = x[v];  
        for(auto to: g[v]) {  
            if(to.first != p && !used[to.first]) {  
                ll val = dfs(to.first, v);  
                if(val%2) {  
                    ans.push_back(to.second);  
                    ret ^= 1;  
                }  
            }     
        }  
        return ret;  
    };  
    bool ok = true;  
    REP(i, n) if(!used[i] && dfs(i, -1)==1) ok = false;  
      
    if(!ok) cout << -1 << endl;  
    else {  
        sort(ALL(ans));  
        cout << ans.size() << "\n";  
        REP(i, ans.size()) cout << ans[i]+1 << (i+1==ans.size() ? '\n' : ' ');  
        cout << flush;  
    }  
  
    return 0;  
}