oj.uz

Submission #392806

# Submission time Handle Problem Language Result Execution time Memory
392806 2021-04-21T18:23:31 Z asbsfds Zagrade (COI17_zagrade) C++14
100 / 100
 1229 ms 49856 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7628 KB Output is correct
2 Correct 6 ms 7628 KB Output is correct
3 Correct 6 ms 7628 KB Output is correct
4 Correct 6 ms 7624 KB Output is correct
5 Correct 6 ms 7628 KB Output is correct
6 Correct 6 ms 7620 KB Output is correct
7 Correct 6 ms 7632 KB Output is correct
8 Correct 6 ms 7700 KB Output is correct
9 Correct 6 ms 7628 KB Output is correct
10 Correct 5 ms 7624 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 38460 KB Output is correct
2 Correct 883 ms 45432 KB Output is correct
3 Correct 596 ms 42696 KB Output is correct
4 Correct 814 ms 44756 KB Output is correct
5 Correct 602 ms 42820 KB Output is correct
6 Correct 698 ms 43720 KB Output is correct
7 Correct 620 ms 42564 KB Output is correct
8 Correct 697 ms 43712 KB Output is correct
9 Correct 608 ms 42584 KB Output is correct
10 Correct 1179 ms 49792 KB Output is correct
11 Correct 496 ms 42692 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7628 KB Output is correct
2 Correct 6 ms 7628 KB Output is correct
3 Correct 6 ms 7628 KB Output is correct
4 Correct 6 ms 7624 KB Output is correct
5 Correct 6 ms 7628 KB Output is correct
6 Correct 6 ms 7620 KB Output is correct
7 Correct 6 ms 7632 KB Output is correct
8 Correct 6 ms 7700 KB Output is correct
9 Correct 6 ms 7628 KB Output is correct
10 Correct 5 ms 7624 KB Output is correct
11 Correct 608 ms 38460 KB Output is correct
12 Correct 883 ms 45432 KB Output is correct
13 Correct 596 ms 42696 KB Output is correct
14 Correct 814 ms 44756 KB Output is correct
15 Correct 602 ms 42820 KB Output is correct
16 Correct 698 ms 43720 KB Output is correct
17 Correct 620 ms 42564 KB Output is correct
18 Correct 697 ms 43712 KB Output is correct
19 Correct 608 ms 42584 KB Output is correct
20 Correct 1179 ms 49792 KB Output is correct
21 Correct 496 ms 42692 KB Output is correct
22 Correct 1227 ms 23992 KB Output is correct
23 Correct 1225 ms 24128 KB Output is correct
24 Correct 1198 ms 24132 KB Output is correct
25 Correct 1229 ms 24024 KB Output is correct
26 Correct 712 ms 30084 KB Output is correct
27 Correct 713 ms 27332 KB Output is correct
28 Correct 719 ms 26252 KB Output is correct
29 Correct 1160 ms 49732 KB Output is correct
30 Correct 1174 ms 49856 KB Output is correct
31 Correct 144 ms 23580 KB Output is correct
32 Correct 507 ms 42748 KB Output is correct