Submission #1190187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190187		Tob	Zagrade (COI17_zagrade)	C++20	100 / 100	186 ms	116868 KiB

zagrade

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 3e5 + 7;

int n;
ll res;
string a;
vector <int> adj[N];
int off[N], ofg[N], siz[N];
map <int, int> f[N], g[N];

void pdfs(int x, int p = -1) {
	siz[x] = 1;
	for (int y : adj[x]) {
		if (y == p) continue;
		pdfs(y, x);
		siz[x] += siz[y];
	}
}

void dfs(int x) {
	for (int y : adj[x]) dfs(y);
	if (adj[x].empty()) {
		if (a[x] == '(') f[x][1] = 1;
		else g[x][1] = 1;
		return;
	}
	swap(off[x], off[adj[x][0]]);
	swap(ofg[x], ofg[adj[x][0]]);
	swap(f[x], f[adj[x][0]]);
	swap(g[x], g[adj[x][0]]);
	int o = 2*(a[x] == '(')-1;
	for (int i = 1; i < adj[x].size(); i++) {
		int y = adj[x][i];
		for (auto z : f[y]) if (g[x].find(z.F+off[y]-ofg[x]+o) != g[x].end()) res += (ll)g[x][z.F+off[y]-ofg[x]+o]*z.S;
		for (auto z : g[y]) if (f[x].find(z.F+ofg[y]-off[x]-o) != f[x].end()) res += (ll)f[x][z.F+ofg[y]-off[x]-o]*z.S;
		for (auto z : f[y]) f[x][z.F+off[y]-off[x]] += z.S;
		for (auto z : g[y]) g[x][z.F+ofg[y]-ofg[x]] += z.S;
	}
	if (a[x] == '(') {
		f[x][-off[x]]++;
		if (g[x].find(-ofg[x]) != g[x].end()) g[x].erase(-ofg[x]);
		off[x]++;
		ofg[x]--;
	}
	else {
		g[x][-ofg[x]]++;
		if (f[x].find(-off[x]) != f[x].end()) f[x].erase(-off[x]);
		off[x]--;
		ofg[x]++;
	}
	if (f[x].find(-off[x]) != f[x].end()) res += f[x][-off[x]];
	if (g[x].find(-ofg[x]) != g[x].end()) res += g[x][-ofg[x]];
}

int main () {
	FIO;
	cin >> n >> a;
	
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y; x--; y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	
	pdfs(0);
	
	for (int i = 0; i < n; i++) {
		sort(all(adj[i]), [&](int x, int y){return siz[x] < siz[y];});
		if (i) adj[i].pop_back();
		reverse(all(adj[i]));
	}
	
	dfs(0);
	
	cout << res << "\n";

	return 0;
}

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