Submission #235720

#	Time	Username	Problem	Language	Result	Execution time	Memory
235720		Kalam	Zagrade (COI17_zagrade)	C++11	100 / 100	1560 ms	47608 KiB

zagrade

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 300000 + 77;
long long A;
int n , sznow , d1[N] , d2[N] , dp1[N] , dp2[N] , sz[N] , T[N];
int root;
char S[N];
bool M[N];
vector < int > adj[N];

void dfsSz(int v , int prev = -1) {
   d1[v] = (prev == -1 ? 0 : d1[prev]) + (S[v] == '(') - (S[v] == ')');
   dp1[v] = (S[v] == '(' ? (prev == -1 ? 0 : min(0 , dp1[prev] + 1)) : dp1[prev] - 1);
   d2[v] = (prev == -1 ? 0 : (prev == root ? ((S[v] == ')') - (S[v] == '(')) : (d2[prev] + ((S[v] == ')') - (S[v] == '(')))));
   dp2[v] = (S[v] == ')' ? (prev == -1 ? 0 : min(0 , dp2[prev] + 1)) : dp2[prev] - 1);
   if(prev == root)
      dp2[v] = (S[v] == ')' ? 0 : -1);
   sz[v] = 1;
   for(int u : adj[v]) {
      if(u == prev || M[u])
         continue ;
      dfsSz(u , v);
      sz[v] += sz[u];
   }
}
void dfsAdd(int v , int prev = -1) {
   if(dp1[v] == 0)
      ++ T[d1[v]];
   for(int u : adj[v])
      if(u != prev && ! M[u])
         dfsAdd(u , v);
}
void dfsGet(int v , int prev = -1) {
   if(dp2[v] == 0)
      A += T[d2[v]];
   for(int u : adj[v])
      if(u != prev && ! M[u])
         dfsGet(u , v);
}
int Centroid(int v , int prev = -1) {
   for(int u : adj[v])
      if(u != prev && !M[u] && sz[u] * 2 > sznow)
         return Centroid(u , v);
   return v;
}
void Decompose(int v) {
   root = v;dfsSz(v);
   sznow = sz[v];
   int c = Centroid(v);
   root = c;dfsSz(c);
   for(int _ = 0;_ < 2;++ _) {
      if(_ == 0)
         if(dp1[c] == 0)
            ++ T[d1[c]];
      for(int u : adj[c])
         if(! M[u])
            dfsGet(u , c) , dfsAdd(u , c);
      if(_ == 1)
         if(dp2[c] == 0)
            A += T[d2[c]];
      for(int i = 0;i <= sznow;++ i)
         T[i] = 0;
      reverse(adj[c].begin() , adj[c].end());
   }
   M[c] = 1;
   for(int v : adj[c])
      if(! M[v])
         Decompose(v);
}

int main() {
   scanf("%d" , & n);
   scanf("%s" , S + 1);
   for(int v , u , i = 1;i < n;++ i)
      scanf("%d %d" , & v , & u) , adj[v].push_back(u) , adj[u].push_back(v);
   Decompose(1);
   printf("%lld\n" , A);
   return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & n);
    ~~~~~^~~~~~~~~~~~
zagrade.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s" , S + 1);
    ~~~~~^~~~~~~~~~~~~~
zagrade.cpp:78:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d" , & v , & u) , adj[v].push_back(u) , adj[u].push_back(v);
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60