oj.uz

Submission #235720

# Submission time Handle Problem Language Result Execution time Memory
235720 2020-05-29T13:35:28 Z Kalam Zagrade (COI17_zagrade) C++11
100 / 100
 1560 ms 47608 KB 
// 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 10 ms 7552 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 11 ms 7424 KB Output is correct
9 Correct 11 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 47396 KB Output is correct
2 Correct 553 ms 47408 KB Output is correct
3 Correct 563 ms 47528 KB Output is correct
4 Correct 557 ms 47552 KB Output is correct
5 Correct 543 ms 47352 KB Output is correct
6 Correct 558 ms 47352 KB Output is correct
7 Correct 563 ms 47608 KB Output is correct
8 Correct 577 ms 47384 KB Output is correct
9 Correct 545 ms 47484 KB Output is correct
10 Correct 510 ms 47300 KB Output is correct
11 Correct 499 ms 47356 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 10 ms 7552 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 11 ms 7552 KB Output is correct
8 Correct 11 ms 7424 KB Output is correct
9 Correct 11 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 552 ms 47396 KB Output is correct
12 Correct 553 ms 47408 KB Output is correct
13 Correct 563 ms 47528 KB Output is correct
14 Correct 557 ms 47552 KB Output is correct
15 Correct 543 ms 47352 KB Output is correct
16 Correct 558 ms 47352 KB Output is correct
17 Correct 563 ms 47608 KB Output is correct
18 Correct 577 ms 47384 KB Output is correct
19 Correct 545 ms 47484 KB Output is correct
20 Correct 510 ms 47300 KB Output is correct
21 Correct 499 ms 47356 KB Output is correct
22 Correct 1560 ms 29048 KB Output is correct
23 Correct 1462 ms 28792 KB Output is correct
24 Correct 1439 ms 28924 KB Output is correct
25 Correct 1502 ms 28812 KB Output is correct
26 Correct 667 ms 35064 KB Output is correct
27 Correct 680 ms 32120 KB Output is correct
28 Correct 712 ms 30968 KB Output is correct
29 Correct 495 ms 47352 KB Output is correct
30 Correct 500 ms 47312 KB Output is correct
31 Correct 127 ms 28524 KB Output is correct
32 Correct 501 ms 47440 KB Output is correct