oj.uz

Submission #562092

# Submission time Handle Problem Language Result Execution time Memory
562092 2022-05-14T05:17:42 Z Koosha_mv Zagrade (COI17_zagrade) C++14
100 / 100
 1113 ms 69516 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99;

int n,m,t,centroid,a[N],cnt[N],sz[N],vis[N];
pair<int,int> dp[N],pd[N];
ll ans;
string s;
vector<int> g[N];

void dfs1(int u,int p){
	sz[u]=1;
	for(auto v : g[u]){
		if(v==p || vis[v]) continue ;
		dfs1(v,u);
		sz[u]+=sz[v];
	}
	if(centroid==0 && 2*sz[u]>=m) centroid=u;
}
void dfs2(int u,int p){
	sz[u]=1;
	dp[u]=dp[p];
	if(s[u]=='(') dp[u].F++,dp[u].S=min(0,dp[u].S+1);
	else dp[u].F--,dp[u].S--;
	for(auto v : g[u]){
		if(v==p || vis[v]) continue ;
		dfs2(v,u);
		sz[u]+=sz[v];
	}
	if(dp[u].S==0){
		ans+=cnt[dp[u].F];
	}
	if(dp[u].F==0 && dp[u].S==0 && t==1){
		ans++;
	}
}
void dfs3(int u,int p){
	pd[u]=pd[p];
	if(s[u]==')') pd[u].F++,pd[u].S=min(0,pd[u].S+1);
	else pd[u].F--,pd[u].S--;
	for(auto v : g[u]){
		if(v==p || vis[v]) continue ;
		dfs3(v,u);
	}
	if(pd[u].S==0){
		cnt[pd[u].F]++;
	}
	if(s[centroid]=='(' && pd[u].F==1 && pd[u].S==0 && t==1){
		ans++;
	}
}
void calc(int u,int _t){
	t=_t;
	f(i,0,m+1) cnt[i]=0;
	pd[u]={0,0};
	if(s[u]=='(') dp[u]={1,0};
	else dp[u]={-1,-1};
	for(auto v : g[u]){
		if(vis[v]) continue ;
		dfs2(v,u);
		dfs3(v,u);
	}
}
void solve(int x,int _m){
	m=_m;
	centroid=0;
	dfs1(x,x);
	int rt=centroid;
	calc(rt,0); reverse(all(g[rt]));
	calc(rt,1);
	vis[rt]=1;
	for(auto v : g[rt]){
		if(vis[v]) continue ;
		solve(v,sz[v]);
	}
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>s;
	s=' '+s;
	f(i,1,n){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	solve(1,n);
	cout<<ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 16 ms 23868 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 14 ms 23860 KB Output is correct
5 Correct 14 ms 23916 KB Output is correct
6 Correct 16 ms 23872 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 65204 KB Output is correct
2 Correct 541 ms 69356 KB Output is correct
3 Correct 471 ms 69516 KB Output is correct
4 Correct 488 ms 69408 KB Output is correct
5 Correct 532 ms 69328 KB Output is correct
6 Correct 555 ms 69380 KB Output is correct
7 Correct 457 ms 69352 KB Output is correct
8 Correct 494 ms 69308 KB Output is correct
9 Correct 492 ms 69424 KB Output is correct
10 Correct 448 ms 69408 KB Output is correct
11 Correct 398 ms 69380 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 16 ms 23868 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 14 ms 23860 KB Output is correct
5 Correct 14 ms 23916 KB Output is correct
6 Correct 16 ms 23872 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 507 ms 65204 KB Output is correct
12 Correct 541 ms 69356 KB Output is correct
13 Correct 471 ms 69516 KB Output is correct
14 Correct 488 ms 69408 KB Output is correct
15 Correct 532 ms 69328 KB Output is correct
16 Correct 555 ms 69380 KB Output is correct
17 Correct 457 ms 69352 KB Output is correct
18 Correct 494 ms 69308 KB Output is correct
19 Correct 492 ms 69424 KB Output is correct
20 Correct 448 ms 69408 KB Output is correct
21 Correct 398 ms 69380 KB Output is correct
22 Correct 1113 ms 46100 KB Output is correct
23 Correct 953 ms 46100 KB Output is correct
24 Correct 1006 ms 46092 KB Output is correct
25 Correct 1010 ms 46104 KB Output is correct
26 Correct 618 ms 53756 KB Output is correct
27 Correct 606 ms 50188 KB Output is correct
28 Correct 624 ms 48900 KB Output is correct
29 Correct 386 ms 69392 KB Output is correct
30 Correct 395 ms 69408 KB Output is correct
31 Correct 99 ms 45668 KB Output is correct
32 Correct 393 ms 69408 KB Output is correct