Submission #81120

#	Time	Username	Problem	Language	Result	Execution time	Memory
81120		farukkastamonuda	Zagrade (COI17_zagrade)	C++14	100 / 100	949 ms	81148 KiB

zagrade

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60