1215F - Radio Stations - CodeForces Solution

#include <bits/stdc++.h>
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define ll long long
const int MAXN = 4*1e5 + 10;
using namespace std;

vector<int> tarjan(const vector<vector<int>>& adj);

struct TwoSat {
  int N;
  vector<vector<int>> E;
  TwoSat(int N) : N(N), E(2 * N) {}
  int neg(int u) const {
    return (u + N) % (2 * N);
  }
  void add_or(int u, int v) {
    E[neg(u)].push_back(v);
    E[neg(v)].push_back(u);
  }
  void add_nand(int u, int v) {
    E[u].push_back(neg(v));
    E[v].push_back(neg(u));
  }
  void add_true(int u) {
    E[neg(u)].emplace_back(u);
  }
  void add_not(int u) {
    add_true(neg(u));
  }
  void add_xor(int u, int v) {
    add_or(u, v);
    add_nand(u, v);
  }
  void add_and(int u, int v) {
    add_true(u);
    add_true(v);
  }
  void add_nor(int u, int v) {
    add_and(neg(u), neg(v));
  }
  void add_xnor(int u, int v) {
    add_xor(u, neg(v));
  }
  // Assumes tarjan sorts SCCs in reverse topological order (u -> v implies scc[v] <= scc[u]).
  pair<bool, vector<bool>> solve() const {
    vector<bool> res(N);
    auto scc = tarjan(E);
    for (int u = 0; u < N; ++u) {
      if (scc[u] == scc[neg(u)]) return {false, {}};
      res[u] = scc[neg(u)] > scc[u];
    }
    return pair(true, res);
  }
};



bool ativo[MAXN];
TwoSat st2(1);


vector<int> tarjan(const vector<vector<int>>& adj) {
  int n = (int)adj.size(), timer = 0, ncomps = 0;
  enum State { unvisited, on_stack, visited };
  vector<State> state(n, unvisited);
  vector<int> low(n), tin(n), scc(n), stk;
  auto dfs = [&](auto&& dfs, int u) -> void {
    low[u] = tin[u] = timer++;
    stk.push_back(u);
    state[u] = on_stack;
    
    for(int v : adj[u]) 
    {
        // se ativo, u não pode pegar aresta direta pra !u
        if(v == st2.neg(u) && ativo[u]) continue;

        if(state[v] == unvisited) 
        {
            dfs(dfs, v);
            low[u] = min(low[u], low[v]);
        } 
        else 
        if(state[v] == on_stack)
            low[u] = min(low[u], tin[v]);
    }

    if(low[u] == tin[u]) {
      int v;
      do {
        v = stk.back();
        stk.pop_back();
        state[v] = visited;
        scc[v] = ncomps;
      } while(v != u);
      ++ncomps;
    }
  };
  for(int u = 0; u < n; ++u) {
    if(state[u] == unvisited) {
      dfs(dfs, u);
    }
  }
  return scc;
}


int cpl[MAXN];

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

    int n, p, M, m;
    cin >> n >> p >> M >> m;

    st2 = TwoSat(p);

    vector<vi> stc(p);

    for(int i=0, u, v; i<n; i++)
    {
        cin >> u >> v;
        u--, v--;

        st2.add_or(u, v);

        stc[u].emplace_back(i);
        stc[v].emplace_back(i);
    }

    
    vii inter, fila;

    for(int i=1, l, r; i<=p; i++)
    {
        cin >> l >> r;
        inter.emplace_back(l, r);

        fila.emplace_back(l, -i);
        fila.emplace_back(r,  i);

        st2.add_not(i-1);
    }


    for(int i=0, u, v; i<m; i++)
    {
        cin >> u >> v;
        u--, v--;
        st2.add_nand(u, v);
    }



    sort(begin(fila), end(fila));
    pair<bool, vector<bool>> ans;
    

    int tot = 0, F;
    bool subindo = true;


    for(auto& [t, i] : fila){
        if(i < 0){
            i *= -1; i--;

            for(auto& x : stc[i]){
                if(!cpl[x]) tot++;
                cpl[x]++;
            }

            ativo[i] = true;
            subindo = true;
        }
        else {
            i--;

            if(subindo && tot >= n)
            {
                ans = st2.solve();
                F = t;
                if(ans.first) break;
            }

            for(auto& x : stc[i]){
                if(cpl[x] == 1) tot--;
                cpl[x]--;
            }

            ativo[i] = false;
            subindo = false;
        }
    }



    if(!ans.first)
    {
        cout << -1 << endl;
        return 0;
    }


    int cnt = 0;
    for(auto x : ans.second) cnt += bool(x);

    cout << cnt << " " << F << endl;

    for(int i=0; i<p; i++)  
        if(ans.second[i])
            cout << i+1 << " ";

    cout << endl;

    return 0;
}