Submission #392806

#	Time	Username	Problem	Language	Result	Execution time	Memory
392806		asbsfds	Zagrade (COI17_zagrade)	C++14	100 / 100	1229 ms	49856 KiB

zagrade

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 3e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
char niz[maxn];
int a[maxn];
vector< int > graph[maxn];
bool bio[maxn];
int dp[maxn];
map< int, int > m;

int cal(int x, int parr) {
	dp[x] = 1;
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren != parr && !bio[tren]) dp[x] += cal(tren, x);
	}
	return dp[x];
}

int fin(int x, int parr, int siz) {
	int sum = 0;
	int maxi = 0;
	int ind = -1;
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren == parr) continue;
		if (bio[tren]) continue;
		
		sum += dp[tren];
		if (dp[tren] > maxi) {
			maxi = dp[tren];
			ind = tren;
		}
	}
	
	if (2 * maxi < siz) return x;
	return fin(ind, x, siz);
}

void update(int x, int parr, int sum, int mini) {
	//printf("update: %d %d %d %d\n", x, parr, sum, mini);
	sum += a[x];
	mini = a[x] + min(mini, 0);
	if (sum >= 0 && mini >= 0) m[sum]++;
	
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren != parr && !bio[tren]) update(tren, x, sum, mini);
	}
}

llint dfs(int x, int parr, int sum, int mini) {
	//printf("dfs: %d %d %d %d\n", x, parr, sum, mini);
	sum += a[x];
	mini = min(mini, sum);
	
	llint out = 0;
	if (mini >= sum) out += m[-sum];
	
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren != parr && !bio[tren]) out += dfs(tren, x, sum, mini);
	}
	return out;
}

llint solve(int x) {
	int siz = cal(x, -1);
	x = fin(x, -1, siz);
	//printf("solve: %d %d\n", x, siz);
	
	llint out = 0;
	m.clear();
	m[0] = 1;
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (bio[tren]) continue;
		
		out += dfs(tren, x, a[x], a[x]);
		update(tren, x, 0, inf);
	}
	if (a[x] == -1) out += m[1];
	
	m.clear();
	for (int i = graph[x].size() - 1; i >= 0; i--) {
		int tren = graph[x][i];
		if (bio[tren]) continue;
		
		out += dfs(tren, x, a[x], a[x]);
		update(tren, x, 0, inf);
	}
	
	bio[x] = true;
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (!bio[tren]) out += solve(tren);
	}
	return out;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf(" %c", niz+i);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	
	for (int i = 1; i <= n; i++) {
		a[i] = (niz[i] == '(' ? 1 : -1);
	}
	memset(bio, false, sizeof bio);
	printf("%lld\n", solve(1));
	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int cal(int, int)':
zagrade.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int fin(int, int, int)':
zagrade.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'void update(int, int, int, int)':
zagrade.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint dfs(int, int, int, int)':
zagrade.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint solve(int)':
zagrade.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zagrade.cpp:116:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |  for (int i = 1; i <= n; i++) scanf(" %c", niz+i);
      |                               ~~~~~^~~~~~~~~~~~~~
zagrade.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

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