Submission #73543407

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define rep(i, x, y) for(int i = (x); i <= (y); ++i)
#define drep(i, x, y) for(int i = (x); i >= (y); --i)
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pii pair<int, int>
#define fi first
#define se second
#define ep emplace_back
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
inline void inc(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline void dec(int &x, int y) { (x -= y) < 0 && (x += mod); }
inline void tim(int &x, int y) { x = (ll)x * y % mod; }
inline int madd(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int msub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mmul(int x, int y) { return (ll)x * y % mod; }
template<typename T> inline void fix(T &x) { x = (x % mod + mod) % mod; }
template<typename T> inline T rd() { T x; cin >> x; return x; }
int n, m, u, v, tot, scc;
int deg[N], dfn[N], low[N], sc[N];
bool ins[N], vis[N];
stack<int> stk;
vector<pii> G[N];
vector<int> st[N], E[N];
inline void dfs(int u) {
    low[u] = dfn[u] = ++tot, stk.push(u), ins[u] = 1;
    for(auto [v, id] : G[u]) {
        if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
        else if(ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int x; scc++;
        do {
            x = stk.top(), stk.pop(), ins[x] = 0;
            sc[x] = scc, st[scc].pb(x);
        } while(x != u);
    }
}
string S;
vector<int> vec;
inline void update() {
    queue<int> q;
    rep(x, 1, n) if(vis[x] && S[x] == '1') q.push(x);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(auto &[v, i] : G[u]) if(S[v] != '1') S[v] = '1', q.push(v), vec.pb(i);
    }
}
int col[2][N], d[2][N];
inline void bfs(int id) {
    queue<int> q;
    vector<int> in(scc + 1);
    rep(i, 1, scc) in[i] = deg[i];
    rep(i, 1, scc) {
        col[id][i] = 0;
        for(int &x : st[i]) col[id][i] |= (S[x] == '1');
    }
    rep(i, 1, scc) if (!in[i]) q.push(i);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int &v : E[u]) {
            col[id][v] |= col[id][u];
            if(!(--in[v])) q.push(v);
        }
    }
    rep(i, 1, scc) for(int &j : E[i]) if(col[id][i] && col[id][j]) d[id][j]++;
}
string s, t;
int tg[N];
inline void clear() {
	scc = 0, tot = 0; while(stk.size()) stk.pop();
    rep(i, 1, n) G[i].clear(), E[i].clear(), st[i].clear(), vis[i] = dfn[i] = low[i] = ins[i] = 0;
    rep(i, 1, n) sc[i] = d[0][i] = d[1][i] = col[0][i] = col[1][i] = tg[i] = deg[i] = 0;
}
inline void read() {
    cin >> n >> s >> t >> m, s = " " + s, t = " " + t;
	clear();
    rep(i, 1, m) {
        cin >> u >> v;
        if(u != v) G[u].pb({v, i});
        else tg[u] = i;
        vis[u] = vis[v] = 1;
    }
}
inline void print(vector<int> S, char ed) {
	for(int i = 0; i < S.size(); ++i)
		cout << S[i] << (i + 1 == S.size() ? ed : ' ');
}
inline void No() { cout << "-1\n"; }
inline void solve() {
    vector<int> vec1, vec2;
    string s1, t1;
    read(); 
    rep(i, 1, n) if(!dfn[i]) dfs(i);
    rep(i, 1, n) for(auto &[j, id] : G[i]) if(sc[i] != sc[j]) E[sc[i]].pb(sc[j]), ++deg[sc[j]];
    bool flg = 0;
    rep(i, 1, n) if(!vis[i] && s[i] != t[i]) flg = 1;
    if(flg) return No();
    S = s, update(), swap(vec1, vec), s1 = S;
    S = t, update(), swap(vec2, vec), t1 = S;
    rep(i, 1, n) flg |= (s1[i] == '0' && t1[i] == '1');
    if(flg) return No();
    S = s, bfs(0), S = t, bfs(1);
    rep(i, 1, scc) {
        if(!col[0][i] && col[1][i]) return No();
        if(col[0][i] && !col[1][i]) {
            if(d[0][i]) continue;
            int pos = -1; for(int &x : st[i]) if(tg[x]) pos = x;
            if(~pos) vec2.pb(tg[pos]), t1[pos] = '1'; else return No();
        }
    }
    S = t1, update();
    for(int &x : vec) vec2.pb(x);
    vec.clear(), reverse(ALL(vec2));
    cout << SZ(vec1) + SZ(vec2) << '\n';
    print(vec1, ' '), print(vec2, '\n');
}
int main() {
    fastio; int T; cin >> T;
    while(T--) solve(); return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void clear()':
./Main.cpp:76:77: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   76 |     rep(i, 1, n) G[i].clear(), E[i].clear(), st[i].clear(), vis[i] = dfn[i] = low[i] = ins[i] = 0;
      |                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
./Main.cpp: In function 'void print(std::vector<int>, char)':
./Main.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i = 0; i < S.size(); ++i)
      |                        ~~^~~~~~~~~~
./Main.cpp:91:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 cout << S[i] << (i + 1 == S.size() ? ed : ' ');
      |                                  ~~~~~~^~~~~~~~~~~
./Main.cpp: In function 'int main()':
./Main.cpp:124:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  124 |     while(T--) solve(); return 0;
      |     ^~~~~
./Main.cpp:124:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  124 |     while(T--) solve(); return 0;
      |                         ^~~~~~

Judge Result