Submission #235308

#	Time	Username	Problem	Language	Result	Execution time	Memory
235308		ArshiaDadras	Zagrade (COI17_zagrade)	C++14	100 / 100	382 ms	119548 KiB

zagrade

/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
map<int, int> mp1[N], mp2[N];
int n, cost1[N], cost2[N];
vector<int> adj[N];
long long ans;

void Swap(int u, int v) {
	swap(mp1[u], mp1[v]);
	swap(mp2[u], mp2[v]);
	swap(cost1[u], cost1[v]);
	swap(cost2[u], cost2[v]);
}

void dfs(int u, int par) {
	int cost = cost1[u];
	for (auto v: adj[u])
		if (v ^ par) {
			dfs(v, u);
			bool rev = mp1[u].size() + mp2[u].size() < mp1[v].size() + mp2[v].size();
			if (rev)
				Swap(u, v);
			for (auto [x, k]: mp1[v])
				if (mp2[u].count(x + cost1[v] - cost2[u]))
					ans += 1LL * k * mp2[u][x + cost1[v] - cost2[u]];
			for (auto [x, k]: mp2[v])
				if (mp1[u].count(x + cost2[v] - cost1[u]))
					ans += 1LL * k * mp1[u][x + cost2[v] - cost1[u]];
			if (rev)
				Swap(u, v);
			cost1[v] += cost, cost2[v] -= cost;
			mp1[v].erase(-cost1[v] - 1);
			mp2[v].erase(-cost2[v] - 1);
			if (rev)
				Swap(u, v);
			for (auto [x, k]: mp1[v])
				mp1[u][x + cost1[v] - cost1[u]] += k;
			for (auto [x, k]: mp2[v])
				mp2[u][x + cost2[v] - cost2[u]] += k;
		}
	if (mp1[u].count(-cost1[u]))
		ans += mp1[u][-cost1[u]];
	if (mp2[u].count(-cost2[u]))
		ans += mp2[u][-cost2[u]];
	if (~cost)
		mp1[u][1 - cost1[u]]++;
	else
		mp2[u][1 - cost2[u]]++;
}

void read_input() {
	cin >> n;
	for (int u = 0; u < n; u++) {
		char c;
		cin >> c;
		if (c == '(') {
			cost1[u]++;
			cost2[u]--;
		}
		else {
			cost1[u]--;
			cost2[u]++;
		}
	}
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[--u].push_back(--v);
		adj[v].push_back(u);
	}
}

void write_output() {
	dfs(0, 0);
	cout << ans;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), write_output();
	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'void dfs(int, int)':
zagrade.cpp:26:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for (auto [x, k]: mp1[v])
              ^
zagrade.cpp:29:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for (auto [x, k]: mp2[v])
              ^
zagrade.cpp:39:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for (auto [x, k]: mp1[v])
              ^
zagrade.cpp:41:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for (auto [x, k]: mp2[v])
              ^

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