fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  4. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  5. #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
  6. #define ALL(v) (v).begin(), (v).end()
  7. #define IS_INF(x)   (std::isinf(x))
  8. #define IS_NAN(x)   (std::isnan(x))
  9. #define fi   first
  10. #define se   second
  11. #define MASK(i) (1LL << (i))
  12. #define BIT(x, i) (((x) >> (i)) & 1)
  13. #define div   ___div
  14. #define next   ___next
  15. #define prev   ___prev
  16. #define left   ___left
  17. #define right   ___right
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<class X, class Y>
  21.     bool minimize(X &x, const Y &y) {
  22.         X eps = 1e-9;
  23.         if (x > y + eps) {
  24.             x = y;
  25.             return true;
  26.         } else return false;
  27.     }
  28. template<class X, class Y>
  29.     bool maximize(X &x, const Y &y) {
  30.         X eps = 1e-9;
  31.         if (x + eps < y) {
  32.             x = y;
  33.             return true;
  34.         } else return false;
  35.     }
  36. template<class T>
  37.     T Abs(const T &x) {
  38.         return (x < 0 ? -x : x);
  39.     }
  40.  
  41. /* Author: Van Hanh Pham */
  42.  
  43. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  44.  
  45. #define MAX   400400
  46. int numItem, numGroup, numInfo;
  47. vector<int> adj[MAX];
  48. int numNode, numComp, cnt;
  49. int low[MAX], num[MAX], compID[MAX], mark[MAX];
  50. stack<int> st;
  51. vector<int> bigAdj[MAX];
  52. int revDeg[MAX];
  53.  
  54. #define MAX_NODE(x) (x)
  55. #define MIN_NODE(x) ((x) <= numItem ? (x) : (x) + numGroup)
  56.  
  57. int getNumber(char *input) {
  58.   int x;
  59.   return sscanf(input, "%d", &x) == 1 ? x : -1;
  60. }
  61.  
  62. void loadGraph(void) {
  63.   scanf("%d%d%d", &numItem, &numGroup, &numInfo);
  64.   FOR(i, 1, numGroup) {
  65.     int x, y; scanf("%d%d", &x, &y);
  66.     adj[MIN_NODE(i + numItem)].push_back(MIN_NODE(x));
  67.     adj[MIN_NODE(i + numItem)].push_back(MIN_NODE(y));
  68.     adj[MAX_NODE(x)].push_back(MAX_NODE(i + numItem));
  69.     adj[MAX_NODE(y)].push_back(MAX_NODE(i + numItem));
  70.   }
  71.  
  72.   char str[10]; memset(str, 0, sizeof str);
  73.   REP(love, numInfo) {
  74.     scanf("%s", str);
  75.     int x = getNumber(str);
  76.     if (x < 0) {
  77.       int group, item; scanf("%d%d", &group, &item);
  78.       if (strcmp(str, "MAX") == 0) {
  79.         adj[MAX_NODE(group)].push_back(item);
  80.       } else {
  81.         adj[item].push_back(MIN_NODE(group));
  82.       }
  83.     } else {
  84.       int y; scanf("%s", str); scanf("%d", &y);
  85.       if (str[0] == '>') swap(x, y);
  86.       adj[MAX_NODE(x)].push_back(MIN_NODE(y));
  87.     }
  88.   }
  89.  
  90.   numNode = numItem + 2 * numGroup;
  91. }
  92.  
  93. void dfs_tarjan(int u) {
  94.   low[u] = num[u] = ++cnt;
  95.   st.push(u);
  96.  
  97.   FORE(it, adj[u]) {
  98.     int v = *it;
  99.     if (compID[v] > 0) continue;
  100.     if (num[v] == 0) {
  101.       dfs_tarjan(v);
  102.       minimize(low[u], low[v]);
  103.     } else minimize(low[u], num[v]);
  104.   }
  105.  
  106.   if (low[u] == num[u]) {
  107.     numComp++;
  108.     while (true) {
  109.       int v = st.top(); st.pop();
  110.       compID[v] = numComp;
  111.       if (v <= numItem) {
  112.         assert(mark[numComp] == 0);
  113.         mark[numComp] = v;
  114.       }
  115.       if (u == v) break;
  116.     }
  117.   }
  118. }
  119.  
  120. void process(void) {
  121.   FOR(i, 1, numNode) if (num[i] == 0) dfs_tarjan(i);
  122.  
  123.   FOR(i, 1, numNode) FORE(jt, adj[i]) if (compID[i] != compID[*jt]) {
  124.     bigAdj[compID[i]].push_back(compID[*jt]);
  125.     revDeg[compID[*jt]]++;
  126.   }
  127.  
  128.   vector<int> res;
  129.   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  130. #define ADD_COMP(x) q.push(make_pair(mark[x], x));
  131.   FOR(i, 1, numComp) if (revDeg[i] == 0) ADD_COMP(i);
  132.   while (!q.empty()) {
  133.     int u = q.top().se; q.pop();
  134.     if (mark[u] > 0) res.push_back(mark[u]);
  135.  
  136.     FORE(it, bigAdj[u]) {
  137.       int v = *it;
  138.       if (--revDeg[v] == 0) ADD_COMP(v);
  139.     }
  140.   }
  141.  
  142.   FORE(it, res) printf("%d ", *it); printf("\n");
  143. }
  144.  
  145. int main(void) {
  146. #ifdef ONLINE_JUDGE 
  147.     freopen("sbbcffffs.inp", "r", stdin);
  148.     freopen("sbbcffffs.out", "w", stdout);
  149. #endif // THEMIS
  150.  
  151.   loadGraph();
  152.   process();
  153.   return 0;
  154. }
  155.  
  156. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
Success #stdin #stdout 0.01s 25520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nfWvZk
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!