제출 #1308842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308842		vili	Zagrade (COI17_zagrade)	C++20	10 / 100	38 ms	12564 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, int> 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++;
	//cout << "cvor "<<cvor <<": "<< add.fr <<' ' << add.se << endl;
	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) {
	//cout << "SOLVE: CVOR " << cvor << endl;
	DFS (cvor);
	int centroid = findcen (cvor, sz[cvor]);
	//cout << "centroid " << centroid << endl;
	f.clear();
	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);
		//for (auto it : f) cout << it.fr.fr <<' '<<it.fr.se<<": "<<it.se<<endl;
		//cout << endl;
		DFScount (graf[centroid][i], {0, 0});
		//cout << ans << endl;
		DFSadd (graf[centroid][i], 1, p);
	}
 
 
	for (int i = 0; i < graf[centroid].size(); i++) {
		if (bio[graf[centroid][i]]) continue;
		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;
		graf[a-1].pb(b-1);
		graf[b-1].pb(a-1);
	}
	solve (0);
	cout << ans << endl;
	return 0;
}

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