Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //author: JainBot27
- //Created on: 08/31/20
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse4,avx,avx2,fma")
- #include <bits/stdc++.h>
- using namespace std;
- #define f first
- #define s second
- #define pb push_back
- #define mp make_pair
- #define ts to_string
- #define ub upper_bound
- #define lb lower_bound
- #define ar array
- #define all(x) x.begin(), x.end()
- #define siz(x) (int)x.size()
- #define FOR(x, y, z) for(int x = (y); x < (z); x++)
- #define ROF(x, y, z) for(int x = (y-1); x >= (z); x--)
- #define F0R(x, z) FOR(x, 0, z)
- #define R0F(x, z) ROF(x, z, 0)
- #define trav(x, y) for(auto&x:y)
- const string nl = "\n";
- using ll = int64_t;
- using vi = vector<int>;
- using vl = vector<ll>;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using str = string;
- using vpii = vector<pii>;
- using vpll = vector<pll>;
- template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
- template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- str ts(char c) { return str(1,c); }
- str ts(bool b) { return b ? "true" : "false"; }
- str ts(const char* s) { return (str)s; }
- str ts(str s) { return s; }
- template<class A> str ts(complex<A> c) {
- stringstream ss; ss << c; return ss.str(); }
- str ts(vector<bool> v) {
- str res = "{"; for(int i = 0;i < (int)v.size(); i++) res += char('0'+v[i]);
- res += "}"; return res; }
- template<size_t SZ> str ts(bitset<SZ> b) {
- str res = ""; for(int i = 0; i < b.size(); i++) res += char('0'+b[i]);
- return res; }
- template<class A, class B> str ts(pair<A,B> p);
- template<class T> str ts(T v) {
- bool fst = 1; str res = "{";
- for (const auto& x: v) {
- if (!fst) res += ", ";
- fst = 0; res += ts(x);
- }
- res += "}"; return res;
- }
- template<class A, class B> str ts(pair<A,B> p) {
- return "("+ts(p.f)+", "+ts(p.s)+")"; }
- void DBG() { cerr << "]" << endl; }
- template<class H, class... T> void DBG(H h, T... t) {
- cerr << ts(h); if (sizeof...(t)) cerr << ", ";
- DBG(t...); }
- #ifdef D
- #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
- #else
- #define dbg(...) 0
- #endif
- const int mxN = 2e5 + 10;
- vi adj[mxN], radj[mxN], o; int ctr, ans[mxN], scc[mxN], vis[mxN], n, m;
- void dfs(int u){
- vis[u] = 1;
- trav(v, adj[u]){
- if(!vis[v])
- dfs(v);
- }
- o.pb(u);
- }
- void dfs2(int u){
- scc[u] = ctr;
- vis[u] = 1;
- trav(v, radj[u]){
- if(!vis[v])
- dfs2(v);
- }
- }
- signed main(){
- ios_base::sync_with_stdio(0); cin.tie(0);
- cin >> n >> m;
- for(int i=0; i < n; i++){
- char c1, c2; int u1, u2; cin >> c1 >> u1 >> c2 >> u2;
- u1--; u2--;
- u1*=2; u2*=2;
- if(c1=='-') u1++;
- if(c2=='-') u2++;
- adj[u1^1].pb(u2);
- adj[u2^1].pb(u1);
- }
- for(int i=0; i < 2*m; i++){
- trav(v, adj[i]){
- radj[v].pb(i);
- }
- }
- for(int i=0; i < 2*m; i++){
- if(!vis[i])
- dfs(i);
- }
- assert(siz(o)==2*m);
- reverse(all(o));
- memset(vis, 0, sizeof(vis));
- for(int i=0; i < 2*m; i++){
- int x=o[i];
- if(!vis[x]){
- dfs2(x);
- ctr++;
- }
- }
- for(int i=0; i < m; i++){
- //cerr << scc[2*i] << " " << scc[2*i+1] << nl;
- if(scc[2*i]==scc[2*i+1]){
- cout << "IMPOSSIBLE" << nl;
- return 0;
- }
- ans[i] = scc[2*i+1] > scc[2*i];
- }
- for(int i=0; i < m; i++){
- cout << (ans[i]?'-':'+') << " ";
- }
- }
- /*
- * Stuff I should try:
- * Is it Monotonic? -> Binary Search
- * Is N small? -> Bitsets or other exponential
- * Edge Cases? Look Carefully
- * Can't figure anything out? Brute Force and see patterns
- * Try to prove greedies
- * Prefix Sums, Amortization, DP, Data Structures
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement