Advertisement
mickypinata

TOCPC2021: Royal Parentheses

Nov 24th, 2021
941
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6.  
  7. const int N = 1e5 + 5;
  8.  
  9. vector<int> adj[N];
  10. pii pttn[2][N]; // (stack count, min/max of stack count)
  11. char str[N];
  12.  
  13. int main(){
  14.  
  15.     int nVertex, st, ed;
  16.     scanf("%d%d%d", &nVertex, &st, &ed);
  17.     for(int i = 1; i < nVertex; ++i){
  18.         int u, v;
  19.         scanf("%d%d", &u, &v);
  20.         adj[u].push_back(v);
  21.         adj[v].push_back(u);
  22.     }
  23.     scanf(" %s", str + 1);
  24.  
  25.     // BFS from st (Index 0 of pttn)
  26.     for(int u = 1; u <= nVertex; ++u){
  27.         pttn[0][u] = pii(1e9, 0);
  28.     }
  29.     queue<int> que;
  30.     pttn[0][st] = str[st] == '(' ? pii(1, 0) : pii(-1, -1);
  31.     que.push(st);
  32.     while(!que.empty()){
  33.         int u = que.front();
  34.         que.pop();
  35.         for(int v : adj[u]){
  36.             if(pttn[0][v] == pii(1e9, 0)){
  37.                 if(str[v] == '('){
  38.                     pttn[0][v].first = pttn[0][u].first + 1;
  39.                 } else {
  40.                     pttn[0][v].first = pttn[0][u].first - 1;
  41.                 }
  42.                 pttn[0][v].second = min(pttn[0][u].second, pttn[0][v].first);
  43.                 que.push(v);
  44.             }
  45.         }
  46.     }
  47.  
  48.     // BFS from ed (Index 1 of pttn)
  49.     for(int u = 1; u <= nVertex; ++u){
  50.         pttn[1][u] = pii(1e9, 0);
  51.     }
  52.     pttn[1][ed] = str[ed] == '(' ? pii(1, 1) : pii(-1, 0);
  53.     que.push(ed);
  54.     while(!que.empty()){
  55.         int u = que.front();
  56.         que.pop();
  57.         for(int v : adj[u]){
  58.             if(pttn[1][v] == pii(1e9, 0)){
  59.                 if(str[v] == '('){
  60.                     pttn[1][v].first = pttn[1][u].first + 1;
  61.                 } else {
  62.                     pttn[1][v].first = pttn[1][u].first - 1;
  63.                 }
  64.                 pttn[1][v].second = max(pttn[1][u].second, pttn[1][v].first);
  65.                 que.push(v);
  66.             }
  67.         }
  68.     }
  69.  
  70.     // Count valid front parentheses
  71.     map<int, int> mp;
  72.     for(int u = 1; u <= nVertex; ++u){
  73.         if(pttn[0][u].second == 0){
  74.             ++mp[pttn[0][u].first];
  75.         }
  76.     }
  77.  
  78.     // Count valid pairs of parentheses
  79.     lli cnt = 0;
  80.     for(int u = 1; u <= nVertex; ++u){
  81.         if(pttn[1][u].second == 0){
  82.             map<int, int>::iterator itr = mp.find(-pttn[1][u].first);
  83.             if(itr != mp.end()){
  84.                 cnt += itr -> second;
  85.             }
  86.         }
  87.     }
  88.     cout << cnt;
  89.  
  90.     return 0;
  91. }
  92.  
Advertisement
RAW Paste Data Copied
Advertisement