Submission #91756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
91756	2018-12-29T21:34:34 Z	jasony123123	Zagrade (COI17_zagrade)	C++11	100 / 100	1417 ms	78892 KB

zagrade

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

const int MAXN = 300099;
int N, A[MAXN];
set<int> adj[MAXN];
int subtreeSize[MAXN];
ll ans = 0;

int computeSSize(int cur, int par) {
	subtreeSize[cur] = 1;
	for (auto neigh : adj[cur]) if (neigh != par)
		subtreeSize[cur] += computeSSize(neigh, cur);
	return subtreeSize[cur];
}
int getCentroid(int cur, int par) {
	computeSSize(cur, par);
	int maxsize = subtreeSize[cur] / 2; // all subtrees must be <= maxsize
	while (true) {
		int next = -1; // is there a child of cur with size > maxsize?
		for (auto neigh : adj[cur]) { // check all childs of cur
			if (neigh != par && subtreeSize[neigh] > maxsize) {
				next = neigh;
				break;
			}
		}
		if (next == -1) { // cur is a centroid
			return cur;
		}
		par = cur;
		cur = next;
	}
	return -10000; // ERROR
}

struct dat {
	int x, u, d;
	dat(int a, int b, int c) : x(a), u(b), d(c) {}
};
void dfs(int i, int p, v<dat> &tab, int pidx) {
	if (pidx == -1) {
		tab.push_back(dat(A[i], A[i], A[i]));
	}
	else {
		dat cur(0, 0, 0);
		cur.x = A[i] + tab[pidx].x;
		cur.u = min(A[i], A[i] + tab[pidx].u);
		cur.d = min(tab[pidx].d, cur.x);
		tab.push_back(cur);
	}
	int iidx = tab.size() - 1;
	for (auto c : adj[i]) if (c != p) {
		dfs(c, i, tab, iidx);
	}
}

void dfsSolve(int root) {
	root = getCentroid(root, -1);
	int R = A[root];
//	cout << root << " root \n";
	v<v<dat>> table;
	map<int, int> cnt;
	for (auto c : adj[root]) {
		table.push_back(v<dat>());
		dfs(c, root, table.back(), -1);
		for (auto t : table.back()) {
			if (t.x + R == 0 && t.u >= 0)
				ans++;
			if (t.x + R == 0 && t.d + R >= 0 && R >= 0)
				ans++;
			if (t.d >= t.x)
				cnt[t.x]++;
		}
	//	cout << c << ":\n";
	//	for (auto t : table.back())
	//		cout << t.x << " x " << t.u << " u " << t.d << " d \n";
	}
	for (auto &sub : table) {
		for (auto t : sub) if (t.d >= t.x)	cnt[t.x]--;
		for (auto t : sub) {
			if (t.u >= 0 && t.x + R >= 0) {
				auto it = cnt.find(-(t.x + R));
				if (it != cnt.end())
					ans += it->second;
			}
		}
		for (auto t : sub) if (t.d >= t.x)	cnt[t.x]++;
	}
	for (int subt : adj[root]) {
		adj[subt].erase(root);
		dfsSolve(subt);
	}
}

int main() {
	io();
	cin >> N;
	string s;
	cin >> s;
	FOR(i, 0, N) A[i + 1] = s[i] == '(' ? 1 : -1;
	FOR(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		adj[a].insert(b), adj[b].insert(a);
	}
	dfsSolve(1);
	cout << ans << "\n";
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	14800 KB	Output is correct
2	Correct	15 ms	14584 KB	Output is correct
3	Correct	15 ms	14588 KB	Output is correct
4	Correct	13 ms	14584 KB	Output is correct
5	Correct	12 ms	14584 KB	Output is correct
6	Correct	13 ms	14584 KB	Output is correct
7	Correct	13 ms	14584 KB	Output is correct
8	Correct	13 ms	14584 KB	Output is correct
9	Correct	13 ms	14584 KB	Output is correct
10	Correct	12 ms	14648 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	589 ms	71628 KB	Output is correct
2	Correct	1125 ms	77452 KB	Output is correct
3	Correct	629 ms	71552 KB	Output is correct
4	Correct	987 ms	75768 KB	Output is correct
5	Correct	624 ms	71764 KB	Output is correct
6	Correct	638 ms	72184 KB	Output is correct
7	Correct	651 ms	71724 KB	Output is correct
8	Correct	594 ms	71728 KB	Output is correct
9	Correct	622 ms	71664 KB	Output is correct
10	Correct	985 ms	78892 KB	Output is correct
11	Correct	845 ms	71932 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	14800 KB	Output is correct
2	Correct	15 ms	14584 KB	Output is correct
3	Correct	15 ms	14588 KB	Output is correct
4	Correct	13 ms	14584 KB	Output is correct
5	Correct	12 ms	14584 KB	Output is correct
6	Correct	13 ms	14584 KB	Output is correct
7	Correct	13 ms	14584 KB	Output is correct
8	Correct	13 ms	14584 KB	Output is correct
9	Correct	13 ms	14584 KB	Output is correct
10	Correct	12 ms	14648 KB	Output is correct
11	Correct	589 ms	71628 KB	Output is correct
12	Correct	1125 ms	77452 KB	Output is correct
13	Correct	629 ms	71552 KB	Output is correct
14	Correct	987 ms	75768 KB	Output is correct
15	Correct	624 ms	71764 KB	Output is correct
16	Correct	638 ms	72184 KB	Output is correct
17	Correct	651 ms	71724 KB	Output is correct
18	Correct	594 ms	71728 KB	Output is correct
19	Correct	622 ms	71664 KB	Output is correct
20	Correct	985 ms	78892 KB	Output is correct
21	Correct	845 ms	71932 KB	Output is correct
22	Correct	1417 ms	56084 KB	Output is correct
23	Correct	1390 ms	56604 KB	Output is correct
24	Correct	1370 ms	55928 KB	Output is correct
25	Correct	1407 ms	56352 KB	Output is correct
26	Correct	706 ms	62436 KB	Output is correct
27	Correct	750 ms	60120 KB	Output is correct
28	Correct	784 ms	59596 KB	Output is correct
29	Correct	1016 ms	78712 KB	Output is correct
30	Correct	1077 ms	78836 KB	Output is correct
31	Correct	332 ms	68856 KB	Output is correct
32	Correct	567 ms	71928 KB	Output is correct