제출 #1308854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308854		vili	Zagrade (COI17_zagrade)	C++20	10 / 100	37 ms	12512 KiB

zagrade

#include <bits/stdc++.h>
#define pb push_back
#define fr first
#define se second
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector <int> vi;
const int maxn=2*1e5+5;

int bio[maxn], sz[maxn], z[maxn];
vi graf[maxn];

void DFS (int cvor, int parent = -1) {
	sz[cvor] = 1;
	for (int i = 0; i < graf[cvor].size(); i++) {
		if (graf[cvor][i] == parent || bio[graf[cvor][i]]) continue;
		DFS (graf[cvor][i], cvor); sz[cvor] += sz[graf[cvor][i]];
	}
}

int findcen (int cvor, int vel, int parent = -1) {
	for (int i = 0; i < graf[cvor].size(); i++) {
		if (graf[cvor][i] == parent || bio[graf[cvor][i]]) continue;
		if (sz[graf[cvor][i]] * 2 > vel) return findcen (graf[cvor][i], vel, cvor);
	}
	bio[cvor] = 1;
	return cvor;
}
ll ans = 0;
map <pii, ll> f;

void DFSadd (int cvor, int predznak, pii add, int parent = -1) {
	if (z[cvor]) add.fr++;
	else if (add.fr > 0) add.fr--;
	else add.se++;
	for (int i = 0; i < graf[cvor].size(); i++) {
		if (graf[cvor][i] == parent || bio[graf[cvor][i]]) continue;
		DFSadd (graf[cvor][i], predznak, add, cvor);
	}
	if (predznak == 1) {
		if (f.find(add) == f.end()) f[add] = 1;
		else f[add]++;
	}
	else f[add]--;
}

void DFScount (int cvor, pii add, int parent = -1) {
	if (z[cvor] && add.se > 0) add.se--;
	else if (z[cvor]) add.fr++;
	else add.se++;
	for (int i = 0; i < graf[cvor].size(); i++) {
		if (graf[cvor][i] == parent || bio[graf[cvor][i]]) continue;
		DFScount (graf[cvor][i], add, cvor);
	}
	if (add.se == 0 && f.find({0, add.fr}) != f.end()) 
		ans += f[{0, add.fr}];
}

void solve (int cvor) {
	DFS (cvor);
	int centroid = findcen (cvor, sz[cvor]);
	
	pii p = {0, 1};
	if (z[centroid]) p = {1, 0};
	for (int i = 0; i < graf[centroid].size(); i++) {
		if (bio[graf[centroid][i]]) continue;
		DFSadd (graf[centroid][i], 1, p);
	}
	if (f.find(p) == f.end()) f[p] = 1;
	else f[p]++;
	ans += f[{0, 0}];
	for (int i = 0; i < graf[centroid].size(); i++) {
		if (bio[graf[centroid][i]]) continue;
		DFSadd (graf[centroid][i], -1, p);
		DFScount (graf[centroid][i], {0, 0});
		DFSadd (graf[centroid][i], 1, p);
	}
	
	for (int i = 0; i < graf[centroid].size(); i++) {
		if (bio[graf[centroid][i]]) continue;
		f.clear();
		solve (graf[centroid][i]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, a, b;
	cin >> n;
	char c;
	for (int i = 0; i < n; i++) {
		cin >> c;
		if (c == '(') z[i] = 1;
	}
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b; 
		a--; b--;
		graf[a].pb(b);
		graf[b].pb(a);
	}
	solve (0);
	cout << ans << endl;
	return 0;
}

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