| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785196 |
2023-07-17T07:04:57 Z |
박영우(#10025) |
Zagrade (COI17_zagrade) |
C++17 |
|
220 ms |
32320 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 303030
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
vector<int> adj[MAX];
int num[MAX];
int vis[MAX];
void make_num(int x, int p = 0) {
num[x] = 1;
for (auto v : adj[x]) if (v != p) {
if (vis[v]) continue;
make_num(v, x);
num[x] += num[v];
}
}
int cnt[2][MAX];
int mx;
ll ans;
void dfs(int x, int c, int low, int sum, int p = 0) {
sum += A[x] * (2 * c - 1);
low = min(low, sum);
if (low == sum) cnt[c][-low]++;
mx = max(mx, -low);
for (auto v : adj[x]) {
if (vis[v]) continue;
if (v == p) continue;
dfs(v, c, low, sum, x);
}
}
void make_tree(int x) {
make_num(x);
int c = x;
int n = num[x];
while (1) {
bool changed = 0;
for (auto v : adj[c]) {
if (vis[v]) continue;
if (num[c] < num[v]) continue;
if (num[v] > n / 2) {
changed = 1;
c = v;
break;
}
}
if (!changed) break;
}
mx = 0;
for (auto v : adj[c]) {
if (vis[v]) continue;
dfs(v, 0, 0, 0, c);
dfs(v, 1, 0, 0, c);
}
int i;
if (A[c] > 0) {
for (i = 1; i <= mx; i++) ans += 1ll * cnt[0][i] * cnt[1][i + 1];
ans += cnt[1][1];
}
else {
for (i = 1; i <= mx; i++) ans += 1ll * cnt[0][i + 1] * cnt[1][i];
ans += cnt[0][1];
}
for (i = 1; i <= mx; i++) cnt[0][i] = cnt[1][i] = 0;
vis[c] = 1;
for (auto v : adj[c]) if (!vis[v]) make_tree(v);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
string s;
cin >> s;
int i, a, b;
for (i = 1; i <= N; i++) A[i] = s[i - 1] == '(' ? 1 : -1;
for (i = 1; i < N; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
make_tree(1);
cout << ans << ln;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
32320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
