# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
370059 |
2021-02-23T06:29:28 Z |
AriaH |
Zagrade (COI17_zagrade) |
C++11 |
|
1214 ms |
92484 KB |
/** Im the best because i work as hard as i possibly can **/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
char C[N];
int n, A[N], hide[N], sub[N];
pii St[N], Fi[N]; /// St[v].F -> min prefix sum chie St[v].S -> sum chie
ll tot, cnt[N];
vector < int > G[N];
vector < int > subtree[N];
void dfs(int v, int P)
{
subtree[v].clear();
sub[v] = 1;
for(auto u : G[v])
{
if(u == P || hide[u]) continue;
dfs(u, v);
sub[v] += sub[u];
}
}
int find(int v, int P, int _n)
{
for(auto u : G[v])
{
if(u == P || hide[u]) continue;
if(sub[u] * 2 > _n) return find(u, v, _n);
}
return v;
}
void calc(int v, int P)
{
St[v].S = St[P].S + A[v];
St[v].F = min(St[P].F + A[v], A[v]);
if(St[v].F >= 0)
{
cnt[St[v].S] ++;
}
for(auto u : G[v])
{
if(u == P || hide[u]) continue;
calc(u, v);
}
}
void calc2(int v, int P, int root)
{
subtree[root].push_back(v);
Fi[v].S = Fi[P].S + A[v];
Fi[v].F = min(Fi[P].F, Fi[v].S);
for(auto u : G[v])
{
if(u == P || hide[u]) continue;
calc2(u, v, root);
}
}
void dec(int v)
{
dfs(v, 0);
int _n = sub[v], centroid = find(v, 0, _n);
///printf("centroid = %d size = %d\n", centroid, _n);
St[0] = Mp(0, 0);
Fi[centroid] = Mp(0, 0);
for(int i = 0; i <= _n; i ++) cnt[i] = 0;
calc(centroid, 0);
for(auto u : G[centroid])
{
if(hide[u]) continue;
calc2(u, centroid, u);
for(auto cu : subtree[u])
{
if(St[cu].F >= 0)
{
cnt[St[cu].S] --;
}
}
for(auto cu : subtree[u])
{
if(Fi[cu].F == Fi[cu].S)
{
tot += cnt[-Fi[cu].F];
}
}
for(auto cu : subtree[u])
{
if(St[cu].F >= 0)
{
cnt[St[cu].S] ++;
}
}
}
hide[centroid] = 1;
tot += cnt[0];
for(auto u : G[centroid])
{
if(hide[u]) continue;
dec(u);
}
}
int main()
{
scanf("%d%s", &n, C);
for(int i = 0; i < n; i ++)
{
A[i + 1] = (C[i] == '('? 1 : -1);
}
for(int i = 1; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
dec(1);
printf("%lld", tot);
return 0;
}
Compilation message
zagrade.cpp: In function 'int main()':
zagrade.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%d%s", &n, C);
| ~~~~~^~~~~~~~~~~~~~~
zagrade.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
141 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14572 KB |
Output is correct |
2 |
Correct |
12 ms |
14572 KB |
Output is correct |
3 |
Correct |
11 ms |
14700 KB |
Output is correct |
4 |
Correct |
12 ms |
14592 KB |
Output is correct |
5 |
Correct |
12 ms |
14572 KB |
Output is correct |
6 |
Correct |
12 ms |
14572 KB |
Output is correct |
7 |
Correct |
12 ms |
14572 KB |
Output is correct |
8 |
Correct |
12 ms |
14700 KB |
Output is correct |
9 |
Correct |
12 ms |
14572 KB |
Output is correct |
10 |
Correct |
11 ms |
14700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
436 ms |
92216 KB |
Output is correct |
2 |
Correct |
431 ms |
92380 KB |
Output is correct |
3 |
Correct |
439 ms |
92252 KB |
Output is correct |
4 |
Correct |
438 ms |
92252 KB |
Output is correct |
5 |
Correct |
447 ms |
92484 KB |
Output is correct |
6 |
Correct |
471 ms |
92252 KB |
Output is correct |
7 |
Correct |
441 ms |
92408 KB |
Output is correct |
8 |
Correct |
469 ms |
92424 KB |
Output is correct |
9 |
Correct |
446 ms |
92252 KB |
Output is correct |
10 |
Correct |
434 ms |
92252 KB |
Output is correct |
11 |
Correct |
434 ms |
92380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14572 KB |
Output is correct |
2 |
Correct |
12 ms |
14572 KB |
Output is correct |
3 |
Correct |
11 ms |
14700 KB |
Output is correct |
4 |
Correct |
12 ms |
14592 KB |
Output is correct |
5 |
Correct |
12 ms |
14572 KB |
Output is correct |
6 |
Correct |
12 ms |
14572 KB |
Output is correct |
7 |
Correct |
12 ms |
14572 KB |
Output is correct |
8 |
Correct |
12 ms |
14700 KB |
Output is correct |
9 |
Correct |
12 ms |
14572 KB |
Output is correct |
10 |
Correct |
11 ms |
14700 KB |
Output is correct |
11 |
Correct |
436 ms |
92216 KB |
Output is correct |
12 |
Correct |
431 ms |
92380 KB |
Output is correct |
13 |
Correct |
439 ms |
92252 KB |
Output is correct |
14 |
Correct |
438 ms |
92252 KB |
Output is correct |
15 |
Correct |
447 ms |
92484 KB |
Output is correct |
16 |
Correct |
471 ms |
92252 KB |
Output is correct |
17 |
Correct |
441 ms |
92408 KB |
Output is correct |
18 |
Correct |
469 ms |
92424 KB |
Output is correct |
19 |
Correct |
446 ms |
92252 KB |
Output is correct |
20 |
Correct |
434 ms |
92252 KB |
Output is correct |
21 |
Correct |
434 ms |
92380 KB |
Output is correct |
22 |
Correct |
1214 ms |
56736 KB |
Output is correct |
23 |
Correct |
1208 ms |
56388 KB |
Output is correct |
24 |
Correct |
1169 ms |
56300 KB |
Output is correct |
25 |
Correct |
1194 ms |
56800 KB |
Output is correct |
26 |
Correct |
525 ms |
76380 KB |
Output is correct |
27 |
Correct |
528 ms |
71528 KB |
Output is correct |
28 |
Correct |
547 ms |
69512 KB |
Output is correct |
29 |
Correct |
424 ms |
92252 KB |
Output is correct |
30 |
Correct |
432 ms |
92252 KB |
Output is correct |
31 |
Correct |
140 ms |
48604 KB |
Output is correct |
32 |
Correct |
428 ms |
92252 KB |
Output is correct |