oj.uz

Submission #26283

# Submission time Handle Problem Language Result Execution time Memory
26283 2017-06-29T04:27:50 Z 김동현(#1101) Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 37344 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, v[300010], s[300010], chk[300010], cnt[300010];
char str[300010];
vector<int> e[300010];

int sf(int x, int p){
	s[x] = 1;
	for(auto &i : e[x]){
		if(i != p && !chk[i]) s[x] += sf(i, x);
	}
	return s[x];
}

int cf(int x, int p, int t){
	for(auto &i : e[x]){
		if(i != p && !chk[i] && s[x] > t / 2) return cf(i, x, t);
	}
	return x;
}

void g(ll &ret, int t, int mv, int x, int p, int d, int mx){
	if(d == mx){
		if(!t) ret += cnt[d];
		else cnt[d]++;
	}
	for(auto &i : e[x]){
		if(i != p && !chk[i]) g(ret, t, mv, i, x, d + mv * v[i], max(mx, d + mv * v[i]));
	}
}

ll f(int x){
	int ts = sf(x, 0);
	x = cf(x, 0, ts);
	chk[x] = 1;
	ll ret = 0;
	fill(cnt, cnt + ts + 1, 0); if(v[x] > 0) cnt[1] = 1;
	for(auto &i : e[x]){
		if(!chk[i]){
			g(ret, 0, -1, i, x, -v[i], max(0, -v[i]));
			g(ret, 1, 1, i, x, v[x] + v[i], max({0, v[x], v[x] + v[i]}));
		}
	}
	fill(cnt, cnt + ts + 1, 0); if(v[x] < 0) cnt[1] = 1;
	for(auto &i : e[x]){
		if(!chk[i]){
			g(ret, 0, 1, i, x, v[i], max(0, v[i]));
			g(ret, 1, -1, i, x, -(v[x] + v[i]), max({0, -v[x], -(v[x] + v[i])}));
		}
	}
	for(auto &i : e[x]) if(!chk[i]) ret += f(i);
	return ret;
}

int main(){
	scanf("%d%s", &n, str + 1);
	for(int i = 1; i <= n; i++) v[i] = 2 * (str[i] == '(') - 1;
	for(int i = 0, x, y; i < n - 1; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	printf("%lld\n", f(1));
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s", &n, str + 1);
                            ^
zagrade.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14032 KB Output is correct
2 Correct 0 ms 14032 KB Output is correct
3 Correct 0 ms 14032 KB Output is correct
4 Correct 3 ms 14032 KB Output is correct
5 Correct 6 ms 14032 KB Output is correct
6 Correct 3 ms 14032 KB Output is correct
7 Correct 3 ms 14032 KB Output is correct
8 Correct 0 ms 14032 KB Output is correct
9 Correct 3 ms 14032 KB Output is correct
10 Correct 9 ms 14032 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 37344 KB Output is correct
2 Correct 643 ms 37344 KB Output is correct
3 Correct 616 ms 37344 KB Output is correct
4 Correct 576 ms 37336 KB Output is correct
5 Correct 579 ms 37344 KB Output is correct
6 Correct 583 ms 37344 KB Output is correct
7 Correct 586 ms 37344 KB Output is correct
8 Correct 579 ms 37344 KB Output is correct
9 Correct 556 ms 37340 KB Output is correct
10 Correct 529 ms 37340 KB Output is correct
11 Correct 553 ms 37340 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14032 KB Output is correct
2 Correct 0 ms 14032 KB Output is correct
3 Correct 0 ms 14032 KB Output is correct
4 Correct 3 ms 14032 KB Output is correct
5 Correct 6 ms 14032 KB Output is correct
6 Correct 3 ms 14032 KB Output is correct
7 Correct 3 ms 14032 KB Output is correct
8 Correct 0 ms 14032 KB Output is correct
9 Correct 3 ms 14032 KB Output is correct
10 Correct 9 ms 14032 KB Output is correct
11 Correct 626 ms 37344 KB Output is correct
12 Correct 643 ms 37344 KB Output is correct
13 Correct 616 ms 37344 KB Output is correct
14 Correct 576 ms 37336 KB Output is correct
15 Correct 579 ms 37344 KB Output is correct
16 Correct 583 ms 37344 KB Output is correct
17 Correct 586 ms 37344 KB Output is correct
18 Correct 579 ms 37344 KB Output is correct
19 Correct 556 ms 37340 KB Output is correct
20 Correct 529 ms 37340 KB Output is correct
21 Correct 553 ms 37340 KB Output is correct
22 Correct 2416 ms 23800 KB Output is correct
23 Correct 2346 ms 23800 KB Output is correct
24 Correct 2549 ms 23800 KB Output is correct
25 Correct 2483 ms 23800 KB Output is correct
26 Execution timed out 3000 ms 32648 KB Execution timed out
27 Halted 0 ms 0 KB -