oj.uz

Submission #81120

# Submission time Handle Problem Language Result Execution time Memory
81120 2018-10-23T20:32:42 Z farukkastamonuda Zagrade (COI17_zagrade) C++14
100 / 100
 949 ms 81148 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
#define pi pair<lo int, int>
using namespace std;
int n, x, y, sz[li], vis[li], mark[li], mark2[li];
char s[li];
int A[li];
lo int ans;
vector<int> v[li], vec, vec2, sil;
int calc(int node, int ata = - 1){
	sz[node] = 0;
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go == ata || vis[go] == 1) continue;
		sz[node] += calc(go, node);
	}
	return ++sz[node];
}
int find(int node, int ata , int siz){
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go != ata && vis[go] == 0 && sz[go] > siz / 2)
			return find(go , node, siz);
	}
	return node;
}
void dfs2(int node, int ata, int sm1, int mn1, int sm2, int mn2){
	sm1 += A[node];
	sm2 -= A[node];
	mn1 = min(mn1, sm1);
	mn2 = min(mn2, sm2);
	if(sm1 <= 0 && sm1 == mn1) ans += 1LL * mark[- sm1];
	if(sm2 <= 0 && sm2 == mn2) ans += 1LL * mark2[- sm2];
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go == ata || vis[go] == 1) continue;
		dfs2(go, node, sm1, mn1, sm2, mn2);
	}
}
void dfs(int node, int ata, int sm1, int mn1, int sm2, int mn2){
	sm1 += A[node];
	sm2 -= A[node];
	mn1 = max(mn1, sm1);
	mn2 = max(mn2, sm2);
	if(sm1 >= 0 && sm1 == mn1) vec.pb(sm1);
	if(sm2 >= 0 && sm2 == mn2) vec2.pb(sm2);
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go == ata || vis[go] == 1) continue;
		dfs(go, node, sm1, mn1, sm2, mn2);
	}
}
void solve(int cur = 1){
	int cen = find(cur , - 1 , calc(cur));
	vis[cen] = 1;
	for(int i = 0; i < (int)v[cen].size() ; i ++){
		int go = v[cen][i];
		if(vis[go] == 1) continue;
		vec.clear();
		vec2.clear();
		dfs2(go , - 1, 0 , inf , 0 ,inf);
		dfs(go , - 1, 0 , - inf, 0, - inf);
		for(int j = 0; j < (int)vec.size(); j ++){
			int git = vec[j];
			if(git + A[cen] >= 0){
				mark[git + A[cen]] ++;
				if(git + A[cen] == 0) ans ++;
				sil.pb(git + A[cen]);
			}
		}
		for(int j = 0; j < (int)vec2.size() ; j ++){
			int git = vec2[j];
			if(git - A[cen] >= 0){
				mark2[git - A[cen]] ++;
				if(git - A[cen] == 0) ans ++;
				sil.pb(git - A[cen]);
			}
		}
	}
	for(int i = 0; i < (int)sil.size(); i ++){
		int go = sil[i];
		mark[go] = 0;
		mark2[go] = 0;
	}
	sil.clear();
	for(int i = 0; i < (int)v[cen].size(); i ++){
		int go = v[cen][i];
		if(vis[go] == 0) solve(go);
	}
}
int main(){
	scanf("%d", &n);
	scanf("%s", s + 1);
	for(int i = 1; i < n; i ++){
		scanf("%d %d", &x ,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i = 1; i <= n ; i++){
		if(s[i] == '(') A[i] = 1;
		else A[i] = - 1;
	}
	solve();
	printf("%lld\n", ans);
	return 0;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
zagrade.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s + 1);
  ~~~~~^~~~~~~~~~~~~
zagrade.cpp:102:8: 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 10 ms 7416 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 9 ms 7612 KB Output is correct
4 Correct 10 ms 7612 KB Output is correct
5 Correct 9 ms 7612 KB Output is correct
6 Correct 9 ms 7612 KB Output is correct
7 Correct 9 ms 7624 KB Output is correct
8 Correct 9 ms 7624 KB Output is correct
9 Correct 9 ms 7684 KB Output is correct
10 Correct 8 ms 7684 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 34936 KB Output is correct
2 Correct 416 ms 36540 KB Output is correct
3 Correct 397 ms 36540 KB Output is correct
4 Correct 417 ms 36540 KB Output is correct
5 Correct 395 ms 36540 KB Output is correct
6 Correct 412 ms 36540 KB Output is correct
7 Correct 401 ms 36540 KB Output is correct
8 Correct 405 ms 36540 KB Output is correct
9 Correct 411 ms 36540 KB Output is correct
10 Correct 395 ms 38580 KB Output is correct
11 Correct 399 ms 38580 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 9 ms 7612 KB Output is correct
4 Correct 10 ms 7612 KB Output is correct
5 Correct 9 ms 7612 KB Output is correct
6 Correct 9 ms 7612 KB Output is correct
7 Correct 9 ms 7624 KB Output is correct
8 Correct 9 ms 7624 KB Output is correct
9 Correct 9 ms 7684 KB Output is correct
10 Correct 8 ms 7684 KB Output is correct
11 Correct 400 ms 34936 KB Output is correct
12 Correct 416 ms 36540 KB Output is correct
13 Correct 397 ms 36540 KB Output is correct
14 Correct 417 ms 36540 KB Output is correct
15 Correct 395 ms 36540 KB Output is correct
16 Correct 412 ms 36540 KB Output is correct
17 Correct 401 ms 36540 KB Output is correct
18 Correct 405 ms 36540 KB Output is correct
19 Correct 411 ms 36540 KB Output is correct
20 Correct 395 ms 38580 KB Output is correct
21 Correct 399 ms 38580 KB Output is correct
22 Correct 881 ms 38580 KB Output is correct
23 Correct 842 ms 38580 KB Output is correct
24 Correct 851 ms 38580 KB Output is correct
25 Correct 949 ms 38580 KB Output is correct
26 Correct 489 ms 46328 KB Output is correct
27 Correct 493 ms 48676 KB Output is correct
28 Correct 497 ms 51776 KB Output is correct
29 Correct 396 ms 71800 KB Output is correct
30 Correct 392 ms 76092 KB Output is correct
31 Correct 131 ms 76092 KB Output is correct
32 Correct 387 ms 81148 KB Output is correct