Submission #419602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
419602	2021-06-07T10:07:31 Z	keta_tsimakuridze	Zagrade (COI17_zagrade)	C++14	100 / 100	1495 ms	52020 KB

zagrade

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,ans,sz[N],c[N],fix[N],n,centroid,ans_;
vector<int>V[N];
map<int,int> cnt;
void get_szs(int u,int p){
	sz[u] = 1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p || fix[V[u][i]]) continue;
		get_szs(V[u][i],u);
		sz[u] += sz[V[u][i]];
	}
}
int find_centroid(int u,int p,int Sz){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p || fix[V[u][i]]) continue;
		if(sz[V[u][i]] >Sz/2) return find_centroid(V[u][i],u,Sz);
	}
	return u;
}
void half2(int u,int p,int cur,int mn,int x,int y) {
	// # of vertices   such that  

	cur += c[u];
	x+=(c[u]==1);
	mn = min(mn,cur);
	y+=(c[u]==-1);
//	y x
	if(y-x >= abs(mn))ans += cnt[y-x];
	if(mn+c[centroid] >= 0 && cur+c[centroid] == 0 )  ans_++;
//	cout<<u<<" "<<cur<<" "<<mn<<" "<<x<<" "<<y<<endl;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i] == p || fix[V[u][i]]) continue;
		// end
		half2(V[u][i],u,cur,mn,x,y);
	}
}
void half1(int u,int p,int cur,int mx,int x,int y) {
	
	cur += c[u];
	x+=(c[u]==1);
	mx = max(mx,cur); 
	y+=(c[u]==-1); //cout<<u<<" "<<x<<" "<<y<<" "<<mx<<endl;
	if(cur-mx >= 0) cnt[x-y]++;
	if(cur-mx >= 0 && cur==0) ans_++;
	for(int i=0;i<V[u].size();i++) {
		if(V[u][i] == p || fix[V[u][i]]) continue;
		half1(V[u][i],u,cur,mx,x,y);
	}
}
void centroid_decomp(int u){
	get_szs(u,0);
	int C = find_centroid(u,0,sz[u]);
	fix[C] = 1; 
	centroid=C;
//	if(C!=2) return;
//	cout<<C<<"++++"<<endl; 
	
	cnt.clear();
	ans_ = 0;
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		half2(V[C][i],C,0,0,0,0);
		half1(V[C][i],C,c[C],max(0ll,c[C]),c[C] == 1,c[C]==-1);
	}// cout<<cnt[{2,0}]<<endl;
	reverse(V[C].begin(),V[C].end());
	cnt.clear();
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		half2(V[C][i],C,0,0,0,0);
		half1(V[C][i],C,c[C],max(0ll,c[C]),c[C] == 1,c[C]==-1);
	} ans += ans_/2; //cout<<ans<<endl;
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		centroid_decomp(V[C][i]);
	}
}
main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='(') c[i] = 1;
		else c[i] = -1;
	}
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
//	dfs(1,0);
	centroid_decomp(1);
	cout<<ans<<endl;
}

Compilation message

zagrade.cpp: In function 'void get_szs(long long int, long long int)':
zagrade.cpp:12:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
zagrade.cpp:19:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void half2(long long int, long long int, long long int, long long int, long long int, long long int)':
zagrade.cpp:36:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void half1(long long int, long long int, long long int, long long int, long long int, long long int)':
zagrade.cpp:50:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void centroid_decomp(long long int)':
zagrade.cpp:65:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:72:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:77:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: At global scope:
zagrade.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7372 KB	Output is correct
2	Correct	6 ms	7372 KB	Output is correct
3	Correct	6 ms	7412 KB	Output is correct
4	Correct	6 ms	7364 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	6 ms	7368 KB	Output is correct
7	Correct	6 ms	7372 KB	Output is correct
8	Correct	6 ms	7372 KB	Output is correct
9	Correct	6 ms	7372 KB	Output is correct
10	Correct	5 ms	7372 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	746 ms	42476 KB	Output is correct
2	Correct	1035 ms	46196 KB	Output is correct
3	Correct	746 ms	42628 KB	Output is correct
4	Correct	994 ms	45348 KB	Output is correct
5	Correct	757 ms	42572 KB	Output is correct
6	Correct	872 ms	44008 KB	Output is correct
7	Correct	764 ms	42532 KB	Output is correct
8	Correct	876 ms	44028 KB	Output is correct
9	Correct	744 ms	42568 KB	Output is correct
10	Correct	1441 ms	51928 KB	Output is correct
11	Correct	683 ms	42504 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7372 KB	Output is correct
2	Correct	6 ms	7372 KB	Output is correct
3	Correct	6 ms	7412 KB	Output is correct
4	Correct	6 ms	7364 KB	Output is correct
5	Correct	6 ms	7372 KB	Output is correct
6	Correct	6 ms	7368 KB	Output is correct
7	Correct	6 ms	7372 KB	Output is correct
8	Correct	6 ms	7372 KB	Output is correct
9	Correct	6 ms	7372 KB	Output is correct
10	Correct	5 ms	7372 KB	Output is correct
11	Correct	746 ms	42476 KB	Output is correct
12	Correct	1035 ms	46196 KB	Output is correct
13	Correct	746 ms	42628 KB	Output is correct
14	Correct	994 ms	45348 KB	Output is correct
15	Correct	757 ms	42572 KB	Output is correct
16	Correct	872 ms	44008 KB	Output is correct
17	Correct	764 ms	42532 KB	Output is correct
18	Correct	876 ms	44028 KB	Output is correct
19	Correct	744 ms	42568 KB	Output is correct
20	Correct	1441 ms	51928 KB	Output is correct
21	Correct	683 ms	42504 KB	Output is correct
22	Correct	1495 ms	25592 KB	Output is correct
23	Correct	1406 ms	25716 KB	Output is correct
24	Correct	1385 ms	25584 KB	Output is correct
25	Correct	1429 ms	25588 KB	Output is correct
26	Correct	832 ms	31368 KB	Output is correct
27	Correct	860 ms	28488 KB	Output is correct
28	Correct	868 ms	27452 KB	Output is correct
29	Correct	1458 ms	52020 KB	Output is correct
30	Correct	1397 ms	51920 KB	Output is correct
31	Correct	226 ms	26544 KB	Output is correct
32	Correct	660 ms	42656 KB	Output is correct