fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 200005;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. int n, k, m;
  41. vector <int> GX[MAXN], GN[MAXN];
  42.  
  43. int par[MAXN];
  44.  
  45. int find_par(int u){
  46.         if(par[u] < 0) return u;
  47.         return par[u] = find_par(par[u]);
  48. }
  49.  
  50. bool join(int u, int v){
  51.         u = find_par(u);
  52.         v = find_par(v);
  53.         if(u == v) return false;
  54.         if(par[u] > par[v]) swap(u, v);
  55.         par[u] += par[v];
  56.         par[v] = u;
  57.         return true;
  58. }
  59.  
  60. struct query{
  61.  
  62.         char x;
  63.         int u, v;
  64.         query(int u = 0, char x = 'a', int v = 0) :
  65.                 u(u), x(x), v(v) {}
  66.  
  67.         void input(void){
  68.  
  69.                 string s; cin >> s;
  70. //                cerr << s << "\n";
  71.  
  72.                 int X = 0, Y = 0;
  73.  
  74.                 x = 'a';
  75.  
  76.                 REP(i, SZ(s)){
  77.                         if(!(s[i] >= '0' && s[i] <= '9'))
  78.                                 x = s[i];
  79.                         else if(x == 'a')
  80.                                 X = X * 10 + s[i] - '0';
  81.                         else
  82.                                 Y = Y * 10 + s[i] - '0';
  83.                 }
  84.  
  85.  
  86.                 u = X;
  87.                 v = Y;
  88.  
  89. //                cout << u << " " << x << " " << v << "\n";
  90.  
  91.         }
  92.  
  93.         void get(int &_u, char &_x, int & _v){
  94.                 _u = u;
  95.                 _x = x;
  96.                 _v = v;
  97.         }
  98.  
  99. }Q[MAXN];
  100.  
  101. int f[MAXN], g[MAXN];
  102.  
  103. void xuoi(int u){
  104.         f[u] = 1;
  105.         for(int v : GX[u]){
  106.                 if(f[v] == -1)
  107.                         xuoi(v);
  108.                 maximize(f[u], f[v] + 1);
  109.         }
  110. }
  111.  
  112. void nguoc(int u){
  113.         g[u] = 1;
  114.         for(int v : GN[u]){
  115.                 if(g[v] == -1)
  116.                         nguoc(v);
  117.                 maximize(g[u], g[v] + 1);
  118.         }
  119. }
  120.  
  121. void solve(void){
  122.         cin >> n >> k >> m;
  123.         FOR(i, 1, n) par[i] = -1;
  124.         FOR(i, 1, m) Q[i].input();
  125.  
  126. //        return;
  127.  
  128.         FOR(i, 1, m){
  129.                 char x;
  130.                 int u, v;
  131.                 Q[i].get(u, x, v);
  132.                 if(x == '=')
  133.                         join(u, v);
  134.         }
  135.  
  136.         FOR(i, 1, m){
  137.                 char x;
  138.                 int u, v;
  139.                 Q[i].get(u, x, v);
  140.  
  141.                 u = find_par(u);
  142.                 v = find_par(v);
  143.  
  144.                 if(x == '<'){
  145.                         GX[v].PB(u);
  146.                         GN[u].PB(v);
  147.                 }
  148.                 else if(x == '>'){
  149.                         GN[v].PB(u);
  150.                         GX[u].PB(v);
  151.                 }
  152.         }
  153.  
  154.         MS(f, -1);
  155.         MS(g, -1);
  156.  
  157.         FOR(i, 1, n){
  158.  
  159.                 int u = find_par(i);
  160.                 if(f[u] == -1)
  161.                         xuoi(u);
  162.                 if(g[u] == -1)
  163.                         nguoc(u);
  164.  
  165.                 int len = f[u] + g[u] - 1;
  166.  
  167.                 if(len == k)
  168.                         cout << char('a' + f[u] - 1);
  169.                 else
  170.                         cout << '?';
  171.         }
  172. }
  173.  
  174. int main(void){
  175.  
  176.         ios_base :: sync_with_stdio(0);
  177.         cin.tie(0); cout.tie(0);
  178.  
  179.         #define TaZinh "test"
  180.  
  181.         if(fopen(TaZinh".inp", "r"))
  182.                 TSun(TaZinh);
  183.  
  184.         int Sun = 1;
  185. //        cin >> Sun;
  186.         REP(love, Sun) solve();
  187.  
  188.         return 0;
  189. }
  190.  
  191.  
Success #stdin #stdout 0.01s 17616KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KahLtn
language:
C++ (gcc 8.3)
created:
86 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!