Submission #419605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
419605	2021-06-07T10:08:47 Z	keta_tsimakuridze	Zagrade (COI17_zagrade)	C++14	100 / 100	1520 ms	52008 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) {

	cur += c[u];
	x+=(c[u]==1);
	mn = min(mn,cur);
	y+=(c[u]==-1);
	if(y-x >= abs(mn))ans += cnt[y-x];
	if(mn+c[centroid] >= 0 && cur+c[centroid] == 0 )  ans_++;

	for(int i=0;i<V[u].size();i++){
		if(V[u][i] == p || fix[V[u][i]]) continue;
	
		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); 
	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;

	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);
	}
	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;
	for(int i=0;i<V[C].size();i++){
		if(fix[V[C][i]]) continue;
		centroid_decomp(V[C][i]);
	}
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	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);
	}
	centroid_decomp(1);
	cout<<ans;
}

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:34: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]
   34 |  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:48: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]
   48 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
zagrade.cpp: In function 'void centroid_decomp(long long int)':
zagrade.cpp:61: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]
   61 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:68: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]
   68 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp:73: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]
   73 |  for(int i=0;i<V[C].size();i++){
      |              ~^~~~~~~~~~~~
zagrade.cpp: At global scope:
zagrade.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main(){
      | ^~~~

Subtask #1

10.0 / 10.0

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

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	640 ms	42552 KB	Output is correct
2	Correct	949 ms	46256 KB	Output is correct
3	Correct	636 ms	42720 KB	Output is correct
4	Correct	840 ms	45296 KB	Output is correct
5	Correct	618 ms	42612 KB	Output is correct
6	Correct	728 ms	43844 KB	Output is correct
7	Correct	603 ms	42692 KB	Output is correct
8	Correct	735 ms	43892 KB	Output is correct
9	Correct	613 ms	42532 KB	Output is correct
10	Correct	1289 ms	51940 KB	Output is correct
11	Correct	527 ms	42564 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	7372 KB	Output is correct
2	Correct	5 ms	7372 KB	Output is correct
3	Correct	5 ms	7372 KB	Output is correct
4	Correct	6 ms	7444 KB	Output is correct
5	Correct	5 ms	7448 KB	Output is correct
6	Correct	7 ms	7372 KB	Output is correct
7	Correct	6 ms	7372 KB	Output is correct
8	Correct	5 ms	7372 KB	Output is correct
9	Correct	7 ms	7372 KB	Output is correct
10	Correct	5 ms	7356 KB	Output is correct
11	Correct	640 ms	42552 KB	Output is correct
12	Correct	949 ms	46256 KB	Output is correct
13	Correct	636 ms	42720 KB	Output is correct
14	Correct	840 ms	45296 KB	Output is correct
15	Correct	618 ms	42612 KB	Output is correct
16	Correct	728 ms	43844 KB	Output is correct
17	Correct	603 ms	42692 KB	Output is correct
18	Correct	735 ms	43892 KB	Output is correct
19	Correct	613 ms	42532 KB	Output is correct
20	Correct	1289 ms	51940 KB	Output is correct
21	Correct	527 ms	42564 KB	Output is correct
22	Correct	1458 ms	25580 KB	Output is correct
23	Correct	1496 ms	25612 KB	Output is correct
24	Correct	1329 ms	25608 KB	Output is correct
25	Correct	1520 ms	25608 KB	Output is correct
26	Correct	701 ms	31380 KB	Output is correct
27	Correct	711 ms	28564 KB	Output is correct
28	Correct	734 ms	27420 KB	Output is correct
29	Correct	1277 ms	52008 KB	Output is correct
30	Correct	1259 ms	51956 KB	Output is correct
31	Correct	115 ms	26496 KB	Output is correct
32	Correct	523 ms	42472 KB	Output is correct