fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=5e5;
  4. int total;
  5. vector<int> adj[N];
  6. int deg[N];
  7. void add(int u,int v)
  8. {
  9.     adj[u].push_back(v);
  10.     deg[v]++;
  11. }
  12. int main()
  13. {
  14.     int n,k,m;
  15.     cin>>n>>k>>m;
  16.     int num=n+k;
  17.     total=n+2*num;
  18.     vector<int> moun[N];
  19.     for(int a=1;a<=n;a++){
  20.         moun[a].push_back(a);
  21.         add(n+a,a);
  22.         add(a,n+a+num);
  23.     }
  24.     for(int a=1;a<=k;a++){
  25.         int idx=n+a;
  26.         int x,y;
  27.         cin>>x>>y;
  28.         set<int> st;
  29.         for(int m:moun[x]){
  30.             st.insert(m);
  31.         }
  32.         for(int m:moun[y]){
  33.             st.insert(m);
  34.         }
  35.         moun[idx].assign(st.begin(),st.end());
  36.         add(n+x,n+idx);
  37.         add(n+y,n+idx);
  38.         add(n+idx+num,n+x+num);
  39.         add(n+idx+num,n+y+num);
  40.     }
  41.     for(int a=0;a<m;a++){
  42.         string type;
  43.         cin>>type;
  44.         if(type=="MAX"){
  45.             int x,y;
  46.             cin>>x>>y;
  47.             for(int u:moun[x]){
  48.                 if(u!=y) add(u,y);
  49.             }
  50.             continue;
  51.         }
  52.         if(type=="MIN"){
  53.             int x,y;
  54.             cin>>x>>y;
  55.             for(int u:moun[x]){
  56.                 if(u!=y) add(y,u);
  57.             }
  58.             continue;
  59.         }
  60.         int x,y;
  61.         x=stoi(type);
  62.         cin>>type>>y;
  63.         if(type=="<") add(n+x+num,n+y);
  64.         else add(n+y+num,n+x);
  65.     }
  66.     priority_queue<int,vector<int>,greater<int>> pq;
  67.     for(int a=1;a<=total;a++){
  68.         if(deg[a]==0) pq.push(a);
  69.     }
  70.     vector<int> ans;
  71.     while(!pq.empty()){
  72.         int u=pq.top();
  73.         pq.pop();
  74.         if(u>=1&&u<=n) ans.push_back(u);
  75.         for(int v:adj[u]){
  76.             deg[v]--;
  77.             if(deg[v]==0) pq.push(v);
  78.         }
  79.     }
  80.     for(int u:ans){
  81.         cout<<u<<" ";
  82.     }
  83.     cout<<"\n";
  84.     for(int a=1;a<=total;a++){
  85.         for(int b:moun[a]){
  86.             cout<<b<<" ";
  87.         }
  88.         cout<<"\n";
  89.     }
  90. }
  91.  
Success #stdin #stdout 0.01s 28308KB
comments (?)
stdin
copy 
7 5 4
2 4
8 1 
3 6
7 3
10 11
12 > 9
MIN 8 4
MAX 12 6
11 < 10
stdout
copy 
1 3 4 2 5 7 6 
1 
2 
3 
4 
5 
6 
7 
2 4 
1 2 4 
3 6 
3 7 
3 6 7
https://ideone.com/LnJ3VJ
language:
C++14 (gcc 8.3)
created:
11 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!