Advertisement
jainbot27

lkjgfksdaf

Sep 1st, 2020
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.88 KB | None | 0 0
  1. //author: JainBot27
  2. //Created on: 08/31/20
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC target("sse4,avx,avx2,fma")
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8.  
  9. #define f first
  10. #define s second
  11. #define pb push_back
  12. #define mp make_pair
  13. #define ts to_string
  14. #define ub upper_bound
  15. #define lb lower_bound
  16. #define ar array
  17. #define all(x) x.begin(), x.end()
  18. #define siz(x) (int)x.size()
  19. #define FOR(x, y, z) for(int x = (y); x < (z); x++)
  20. #define ROF(x, y, z) for(int x = (y-1); x >= (z); x--)
  21. #define F0R(x, z) FOR(x, 0, z)
  22. #define R0F(x, z) ROF(x, z, 0)
  23. #define trav(x, y) for(auto&x:y)
  24.  
  25.  
  26. const string nl = "\n";
  27. using ll = int64_t;
  28. using vi = vector<int>;
  29. using vl = vector<ll>;
  30. using pii = pair<int, int>;
  31. using pll = pair<ll, ll>;
  32. using str = string;
  33. using vpii = vector<pii>;
  34. using vpll = vector<pll>;
  35.  
  36.  
  37. template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
  38. template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
  39. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  40.  
  41.  
  42. str ts(char c) { return str(1,c); }
  43. str ts(bool b) { return b ? "true" : "false"; }
  44. str ts(const char* s) { return (str)s; }
  45. str ts(str s) { return s; }
  46. template<class A> str ts(complex<A> c) {
  47.     stringstream ss; ss << c; return ss.str(); }
  48. str ts(vector<bool> v) {
  49.     str res = "{"; for(int i = 0;i < (int)v.size(); i++) res += char('0'+v[i]);
  50.     res += "}"; return res; }
  51. template<size_t SZ> str ts(bitset<SZ> b) {
  52.     str res = ""; for(int i = 0; i < b.size(); i++) res += char('0'+b[i]);
  53.     return res; }
  54. template<class A, class B> str ts(pair<A,B> p);
  55. template<class T> str ts(T v) {
  56.     bool fst = 1; str res = "{";
  57.     for (const auto& x: v) {
  58.         if (!fst) res += ", ";
  59.         fst = 0; res += ts(x);
  60.     }
  61.     res += "}"; return res;
  62. }
  63. template<class A, class B> str ts(pair<A,B> p) {
  64.     return "("+ts(p.f)+", "+ts(p.s)+")"; }
  65. void DBG() { cerr << "]" << endl; }
  66. template<class H, class... T> void DBG(H h, T... t) {
  67.     cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  68.     DBG(t...); }
  69.  
  70.  
  71. #ifdef D
  72. #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  73. #else
  74. #define dbg(...) 0
  75. #endif
  76.  
  77. const int mxN = 2e5 + 10;
  78. vi adj[mxN], radj[mxN], o; int ctr, ans[mxN], scc[mxN], vis[mxN], n, m;
  79.  
  80. void dfs(int u){
  81.     vis[u] = 1;
  82.     trav(v, adj[u]){
  83.         if(!vis[v])
  84.             dfs(v);
  85.     }
  86.     o.pb(u);
  87. }
  88. void dfs2(int u){
  89.     scc[u] = ctr;
  90.     vis[u] = 1;
  91.     trav(v, radj[u]){
  92.         if(!vis[v])
  93.             dfs2(v);
  94.     }
  95. }
  96. signed main(){
  97.     ios_base::sync_with_stdio(0); cin.tie(0);
  98.     cin >> n >> m;
  99.     for(int i=0; i < n; i++){
  100.         char c1, c2; int u1, u2; cin >> c1 >> u1 >> c2 >> u2;
  101.         u1--; u2--;
  102.         u1*=2; u2*=2;
  103.         if(c1=='-') u1++;
  104.         if(c2=='-') u2++;
  105.         adj[u1^1].pb(u2);
  106.         adj[u2^1].pb(u1);
  107.     }
  108.     for(int i=0; i < 2*m; i++){
  109.         trav(v, adj[i]){
  110.             radj[v].pb(i);
  111.         }
  112.     }
  113.     for(int i=0; i < 2*m; i++){
  114.         if(!vis[i])
  115.             dfs(i);
  116.     }
  117.     assert(siz(o)==2*m);
  118.     reverse(all(o));
  119.     memset(vis, 0, sizeof(vis));
  120.     for(int i=0; i < 2*m; i++){
  121.         int x=o[i];
  122.         if(!vis[x]){
  123.             dfs2(x);
  124.             ctr++;
  125.         }
  126.     }
  127.     for(int i=0; i < m; i++){
  128.         //cerr << scc[2*i] << " " << scc[2*i+1] << nl;
  129.         if(scc[2*i]==scc[2*i+1]){
  130.             cout << "IMPOSSIBLE" << nl;
  131.             return 0;
  132.         }
  133.         ans[i] = scc[2*i+1] > scc[2*i];
  134.     }
  135.     for(int i=0; i < m; i++){
  136.         cout << (ans[i]?'-':'+') << " ";
  137.     }
  138. }
  139.  
  140. /*
  141.  * Stuff I should try:
  142.  * Is it Monotonic? -> Binary Search
  143.  * Is N small? -> Bitsets or other exponential
  144.  * Edge Cases? Look Carefully
  145.  * Can't figure anything out? Brute Force and see patterns
  146.  * Try to prove greedies
  147.  * Prefix Sums, Amortization, DP, Data Structures
  148. */
  149.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement