fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. #define maxN 100007
  9.  
  10. int n, m, k;
  11.  
  12. int sz[maxN];
  13. int par[maxN];
  14. string op[maxN];
  15. vector<int>groupPar;
  16. int groupLeadChar[maxN] = {0};
  17. vector<int>adj[maxN];
  18. vector<int>realAdj[maxN];
  19. int dp[maxN] = {0};
  20.  
  21. void make_set(int u)
  22. {
  23.     sz[u] = 1;
  24.     par[u] = u;
  25. }
  26.  
  27. int find_set(int u)
  28. {
  29.     if(par[u] == u) return u;
  30.     int p = find_set(par[u]);
  31.     par[u] = p;
  32.     return p;
  33. }
  34.  
  35. void union_set(int u, int v)
  36. {
  37.     if(u == v)
  38.         return;
  39.     if(sz[u] < sz[v])
  40.         swap(u, v);
  41.     sz[u] += sz[v];
  42.     par[v] = u;
  43. }
  44.  
  45. void readData()
  46. {
  47.     cin >> n >> k >> m;
  48.     for(int i = 1; i <= m; i++)
  49.         cin >> op[i];
  50. }
  51.  
  52. void dsu()
  53. {
  54.     for(int i = 1; i <= m; i++)
  55.     {
  56.         int equalPos = -1;
  57.         for(int j = 0; j < op[i].size(); j++)
  58.             if(op[i][j] == '=')
  59.                 equalPos = j;
  60.         if(equalPos == -1) continue;
  61.         int group1 = 0, group2 = 0;
  62.         for(int j = 0; j < equalPos; j++)
  63.             group1 = group1*10+op[i][j]-'0';
  64.         for(int j = equalPos+1; j < op[i].size(); j++)
  65.             group2 = group2*10+op[i][j]-'0';
  66.         union_set(group1, group2);
  67.     }
  68. }
  69.  
  70. int dfs(int u)
  71. {
  72.     if (dp[u] > 0) return dp[u];
  73.     int res = 1;
  74.     for (int v : adj[u])
  75.         res = max(res, 1 + dfs(v));
  76.     return dp[u] = res;
  77. }
  78.  
  79. void dfsAns(int u, int h)
  80. {
  81.     groupLeadChar[u] = h;
  82.     for(int v: realAdj[u])
  83.         dfsAns(v, h+1);
  84. }
  85.  
  86. void solve()
  87. {
  88.     for(int i = 1; i <= n; i++)
  89.     {
  90.         int par = find_set(i);
  91.         groupPar.push_back(par);
  92.     }
  93.     sort(groupPar.begin(), groupPar.end());
  94.     auto it = unique(groupPar.begin(), groupPar.end());
  95.     groupPar.erase(it, groupPar.end());
  96.     for(int i = 1; i <= m; i++)
  97.     {
  98.         int opPos = -1;
  99.         for(int j = 0; j < op[i].size(); j++)
  100.             if(op[i][j] == '>' || op[i][j] == '<')
  101.                 opPos = j;
  102.         if(opPos == -1)
  103.             continue;
  104.         int group1 = 0, group2 = 0;
  105.         for(int j = 0; j < opPos; j++)
  106.             group1 = group1*10+op[i][j]-'0';
  107.         for(int j = opPos+1; j < op[i].size(); j++)
  108.             group2 = group2*10+op[i][j]-'0';
  109.         group1 = find_set(group1);
  110.         group2 = find_set(group2);
  111.         if(op[i][opPos] == '<')
  112.             adj[group1].push_back(group2);
  113.         else adj[group2].push_back(group1);
  114.     }
  115.     for(int i = 0; i < groupPar.size(); i++)
  116.     {
  117.         adj[0].push_back(groupPar[i]);
  118.         adj[groupPar[i]].push_back(n+1);
  119.     }
  120.     //for(int i = 0; i < groupPar.size(); i++)
  121.     //    cout << groupPar[i] << " ";
  122.     dfs(0);
  123.     /*for(int i = 0; i <= n; i++)
  124.     {
  125.         cout << i << "-> ";
  126.         for(int j = 0; j < adj[i].size(); j++)
  127.             cout << adj[i][j] << " ";
  128.         cout << "\n";
  129.     }*/
  130.     if(dp[0] - 2 < k)
  131.     {
  132.         for(int i = 1; i <= n; i++)
  133.             cout << "?";
  134.         return;
  135.     }
  136.     queue<int>q;
  137.     q.push(0);
  138.     while(!q.empty())
  139.     {
  140.         int u = q.front();
  141.         q.pop();
  142.         for(int v : adj[u])
  143.         {
  144.             if(dp[v] + 1 == dp[u])
  145.             {
  146.                 realAdj[u].push_back(v);
  147.                 q.push(v);
  148.             }
  149.         }
  150.     }
  151.     /*for(int i = 0; i <= n; i++)
  152.     {
  153.         cout << i << "-> ";
  154.         for(int j = 0; j < realAdj[i].size(); j++)
  155.             cout << realAdj[i][j] << " ";
  156.         cout << "\n";
  157.     }*/
  158.     string ans = " ";
  159.     for(int i = 1; i <= n; i++)
  160.         ans += '?';
  161.     dfsAns(0, 0);
  162.     for(int i = 1; i <= n; i++)
  163.     {
  164.         int par = find_set(i);
  165.         if(1 <= groupLeadChar[par] && groupLeadChar[par] <= k)
  166.             ans[i] = ('a'+groupLeadChar[par]-1);
  167.     }
  168.     for(int i = 1; i <= n; i++)
  169.         cout << ans[i];
  170. }
  171.  
  172. int main()
  173. {
  174.     ios_base::sync_with_stdio(0);
  175.     cin.tie(0);
  176.     readData();
  177.     for(int i = 0; i <= n+1; i++)
  178.         make_set(i);
  179.     dsu();
  180.     solve();
  181.     return 0;
  182. }
  183.  
Success #stdin #stdout 0.01s 11800KB
comments (?)
stdin
copy 
4 3 2
1<2
2<3
stdout
copy 
abc?
https://ideone.com/TVblvv
language:
C++14 (gcc 8.3)
created:
6 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!