oj.uz

Submission #81119

# Submission time Handle Problem Language Result Execution time Memory
81119 2018-10-23T20:30:00 Z farukkastamonuda Zagrade (COI17_zagrade) C++14
10 / 100
 416 ms 78944 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 ans, A[li];
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 += mark[- sm1];
	if(sm2 <= 0 && sm2 == mn2) ans += 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("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 35292 KB Output is correct
2 Correct 411 ms 41004 KB Output is correct
3 Correct 388 ms 43600 KB Output is correct
4 Correct 404 ms 49052 KB Output is correct
5 Correct 383 ms 52092 KB Output is correct
6 Correct 402 ms 56928 KB Output is correct
7 Correct 385 ms 60456 KB Output is correct
8 Correct 396 ms 65196 KB Output is correct
9 Correct 385 ms 68884 KB Output is correct
10 Correct 392 ms 76552 KB Output is correct
11 Incorrect 381 ms 78944 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7540 KB Output is correct
3 Correct 9 ms 7660 KB Output is correct
4 Correct 9 ms 7796 KB Output is correct
5 Correct 9 ms 7840 KB Output is correct
6 Correct 9 ms 7840 KB Output is correct
7 Correct 9 ms 7864 KB Output is correct
8 Correct 9 ms 8004 KB Output is correct
9 Correct 9 ms 8004 KB Output is correct
10 Correct 9 ms 8004 KB Output is correct
11 Correct 416 ms 35292 KB Output is correct
12 Correct 411 ms 41004 KB Output is correct
13 Correct 388 ms 43600 KB Output is correct
14 Correct 404 ms 49052 KB Output is correct
15 Correct 383 ms 52092 KB Output is correct
16 Correct 402 ms 56928 KB Output is correct
17 Correct 385 ms 60456 KB Output is correct
18 Correct 396 ms 65196 KB Output is correct
19 Correct 385 ms 68884 KB Output is correct
20 Correct 392 ms 76552 KB Output is correct
21 Incorrect 381 ms 78944 KB Output isn't correct