Advertisement
ismaeil

Panda Chess

Oct 7th, 2021
745
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. map<string , set< string > > al;
  5. vector< string > q ,p;
  6. map<string , int> in;
  7. int n ,m ,d;
  8.  
  9. vector< string > topoSort()
  10. {
  11.     unordered_set< string > pq;
  12.     for(auto i : al){
  13.         pq.insert(i.first);
  14.         for(auto j : i.second){
  15.             pq.insert(j);
  16.         }
  17.     }
  18.  
  19.     for(auto i : al){
  20.         for(auto j : i.second){
  21.             in[j] += 1;
  22.             pq.erase(j);
  23.         }
  24.     }
  25.  
  26.     vector< string > topo;
  27.     while( !pq.empty() )
  28.     {
  29.         string u = *pq.begin();
  30.         pq.erase(pq.begin());
  31.  
  32.         topo.push_back(u);
  33.  
  34.         for(auto v : al[u])
  35.         {
  36.             in[v] -= 1;
  37.             if( in[v] == 0 ){
  38.                 pq.insert(v);
  39.             }
  40.         }
  41.     }
  42.  
  43.     return topo;
  44. }
  45.  
  46. int LIS()
  47. {
  48.     map<string , int> idx;
  49.     for(int i = 0 ; i < n ; i++) idx[ q[i] ] = i;
  50.  
  51.     set< int > lis;
  52.     for(int i = 0 ; i < n ; i++)
  53.     {
  54.         if( idx.count( p[i] ) )
  55.         {
  56.             auto it = lis.upper_bound(idx[ p[i] ]);
  57.  
  58.             if( it != lis.end() ) lis.erase(it);
  59.  
  60.             lis.insert(idx[ p[i] ]);
  61.         }
  62.     }
  63.  
  64.     return lis.size();
  65. }
  66.  
  67. int main()
  68. {
  69.     cin >> n >> m >> d;
  70.     for(int i = 0 ; i < m ; i++)
  71.     {
  72.         string u; cin >> u;
  73.         string v; cin >> v;
  74.  
  75.         al[u].insert(v);
  76.     }
  77.  
  78.     p.resize(n);
  79.     for(auto &i : p) cin >> i;
  80.  
  81.     q = topoSort();
  82.  
  83.     cout << 2 * (n - LIS());
  84.     return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement