// compile: make data // run: ./data < data.in #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #ifdef LOCAL #include <debug/codeforces.h> #define debug(x...) _debug_print(#x, x); #define Debug(x...) _debug_print_format(#x, x); #else #define debug(x...) #define Debug(x...) #endif template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;} #define VI vector<int> #define VII vector<vector<int>> #define VIII vector<vector<vector<int>>> #define rep(i,a,b) for(int i=(a);i<(int)(b);++i) #define sz(v) ((int)(v).size()) #define print(...) print_(__VA_ARGS__); #define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0) #define cmin(x,...) x=min({(x), __VA_ARGS__}) #define cmax(x,...) x=max({(x), __VA_ARGS__}) #define INTMAX (int)(9223372036854775807) #define INF (int)(1152921504606846976) #define double long double #define int long long #define MAXN 200010 struct graph { struct node { int v, w; bool operator<(const node &other) const { return w < other.w; } bool operator==(const node &other) const { return v == other.v && w == other.w; } }; vector<vector<node>> e; int n; bool directed; graph(int V, bool D = 0) { n = V; e.resize(n); directed = D; } void add_edge(int u, int v, int w = 1) { e[u].push_back(node{v, w}); } void tarjan_scc(vector<vector<int>> &scc, vector<int> &belong) { stack<int> s; vector<int> dfn(n), low(n), instack(n); int dfncnt; scc.clear(), belong.resize(n, -1); function<void(int)> dfs = [&](int u) { low[u] = dfn[u] = ++dfncnt, s.push(u), instack[u] = 1; for (auto edge: e[u]) { int v = edge.v; if (!dfn[v]) dfs(v), cmin(low[u], low[v]); else if (instack[v]) cmin(low[u], dfn[v]); } if (dfn[u] == low[u]) { scc.push_back(vector<int>{}); while (s.top() != u) { belong[s.top()] = sz(scc) - 1; scc.back().push_back(s.top()); instack[s.top()] = 0, s.pop(); } belong[s.top()] = sz(scc) - 1; scc.back().push_back(s.top()); instack[s.top()] = 0, s.pop(); } }; rep(i, 0, n) if (!~belong[i]) dfs(i); } int topo(vector<int> &vs) { vector<int> din(n, 0); for (auto es: e) for (auto edge: es) ++din[edge.v]; queue<int> q; rep(i, 0, n) if (!din[i]) q.push(i); vs.clear(); while (!q.empty()) { int u = q.front(); q.pop(); vs.push_back(u); for (auto [v, _]: e[u]) { if (!--din[v]) q.push(v); } } return sz(vs) == n; } graph contract(vector<vector<int>> &scc, vector<int> &belong) { tarjan_scc(scc, belong); int V = sz(scc); graph dag(V, 1); vector<int> vis(V, 0); for (auto comp: scc) { for (auto u: comp) { for (auto edge: e[u]) { int v = edge.v; if (belong[u] != belong[v]) { dag.add_edge(belong[u], belong[v]); vis[belong[v]] = 1; } } } for (auto u: comp) for (auto edge: e[u]) if (belong[u] != belong[edge.v]) vis[belong[edge.v]] = 0; } return dag; } int twosat(vector<int> &ans) { vector<vector<int>> scc; vector<int> belong; auto dag = contract(scc, belong); int V = n >> 1; rep(i, 0, V) if (belong[i] == belong[i + V]) return 0; vector<int> vs; dag.topo(vs); vector<int> idx(dag.n); rep(i, 0, dag.n) idx[vs[i]] = i; ans.assign(V, 0); rep(i, 0, V) if (idx[belong[i]] > idx[belong[i + V]]) ans[i] = 1; return 1; } void graphviz_dump(string filename = "graph.dot") { ofstream gf; gf.open(filename); gf << (directed ? "digraph" : "graph") << " {\n"; gf << " "; rep(i, 0, n) gf << i << " ;"[i==n-1]; gf << endl; string notation = directed ? " -> " : " -- "; bool weighted = 0; for (auto es: e) for (auto edge: es) if (edge.w != 1) weighted = 1; rep(u, 0, n) { for (auto [v, w]: e[u]) { if (!directed && u > v) continue; gf << " " << u << notation << v << (weighted ? " ;\n" : ";\n"); } } gf << "}\n"; } }; int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; graph g(2*m, 1); rep(i, 0, n) { string su, sv; int u, v; cin >> su >> u >> sv >> v; --u, --v; if (su[0] == '+' && sv[0] == '+') g.add_edge(m+u, v), g.add_edge(m+v, u); else if (su[0] == '-' && sv[0] == '-') g.add_edge(u, m+v), g.add_edge(v, m+u); else if (su[0] == '+' && sv[0] == '-') g.add_edge(m+u, m+v), g.add_edge(v, u); else if (su[0] == '-' && sv[0] == '+') g.add_edge(u, v), g.add_edge(m+v, m+u); } // g.graphviz_dump(); vector<int> ans; int valid = g.twosat(ans); if (!valid) cout << "IMPOSSIBLE" << endl; else { rep(i, 0, m) cout << (ans[i] ? '+' : '-') << " "; cout << endl; } return 0; }
No Comments