oj.uz

답안 #785196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785196 2023-07-17T07:04:57 Z 박영우(#10025) Zagrade (COI17_zagrade) C++17
0 / 100
 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;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 32320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -