Submission #230901

#	Time	Username	Problem	Language	Result	Execution time	Memory
230901		blacktulip	Zagrade (COI17_zagrade)	C++17	0 / 100	433 ms	36216 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define int long long
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,t,vis[li],sub[li];
int cev;
char s[li];
map<int,int> mpp,mpp1;
vector<int> v[li];

inline void dfs(int node,int ata){
	sub[node]=1;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		dfs(go,node);
		sub[node]+=sub[go];
	}
}

inline int find_centroid(int node,int ata,int sz){
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go]==1)continue;
		if(sub[go]>sz/2)return find_centroid(go,node,sz);
		dfs(go,node);
	}
	return node;
}

inline void upd1(int node,int ata,int der,int mx){
	if(der>=0 && der>=mx)mpp[der]++;
	
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		int at=der+(s[go]==')'?1:-1);
		if(at<0)continue;
		upd1(go,node,at,max(at,mx));
	}
}

inline void upd2(int node,int ata,int der,int kts,int mx){
	//~ cout<<der<<"whyy"<<endl;
	if(kts==0 && der>=0 && der>=mx)mpp[der]--;
	if(kts==1 && der>=0 && der>=mx)mpp[der]++;
	
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		int at=der+(s[go]==')'?1:-1);
		if(at<0)continue;
		upd2(go,node,at,kts,max(mx,at));
	}
}

inline void query(int node,int ata,int der){
	//~ cout<<"()"<<der<<"()"<<node<<"()"<<mpp[0]<<"()"<<endl;
	if(der>=0)cev+=mpp[der];
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		//~ if(go==4){cout<<"mpp"<<mpp[0]<<"mpp"<<endl;}
		int at=der+(s[go]==')'?-1:1);
		query(go,node,at);
	}
}

inline void dfs2(int node,int ata,int der,int der1,int flag){
	if(der==0 && flag==1)cev++;
	if(der1==0 && flag==0)cev++;
	//~ cout<<der1<<"&&"<<endl;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		if(vis[go])continue;
		if(flag==1 && der+(s[go]==')'?-1:1)<0){continue;}
		if(flag==0 && der1+(s[go]==')'?1:-1)<0){continue;}
		dfs2(go,node,der+(s[go]==')'?-1:1),der1+(s[go]==')'?1:-1),flag);
	}
	
}

inline void solve(int node){
	dfs(node,0);
	//~ cout<<node<<endl;
	int c=find_centroid(node,0,sub[node]);
	mpp.clear();
	mpp1.clear();
	//~ mpp[0]++;
	//~ cout<<c<<" : ; "<<s[c]<<endl;
	//~ int at=(s[c]==')'?-1:1);
	//~ int at1=(s[c]==')'?1:-1);
	//~ cout<<at1<<"()()"<<endl;
	upd1(c,0,0,0);
	//~ cout<<mpp[0]<<"why\n";
	//~ dfs2(c,0,at,at1,(at>at1?1:0));
	//~ cout<<cev<<"**\n";
	//~ cout<<c<<"()\n";
	for(int i=0;i<(int)v[c].size();i++){
		int go=v[c][i];
		if(vis[v[c][i]])continue;
		//~ int okk=0,okk1=0;
		//~ cout<<"OO"<<c<<"OO"<<go<<"OO\n";
		if(s[go]==')'){
			//~ cout<<"**\n";
			upd2(go,c,1,0,0);
			//~ cout<<"II"<<mpp[0]<<"II"<<endl;
			query(go,c,-1+(s[c]=='('?1:-1));
		}
		else{
			//~ upd2(go,c,-1,0);
			query(go,c,1+(s[c]=='('?1:-1));
		}
		
		if(s[go]==')'){
			upd2(go,c,1,1,0);
		}
		else{
			//~ upd2(go,c,-1,1);
		}
		//~ cout<<cev<<"**"<<endl;
		
	}
	//~ printf("\n");
	vis[c]=1;
	for(int i=0;i<(int)v[c].size();i++){
		if(vis[v[c][i]])continue;
		solve(v[c][i]);
	}
	
}

main(void){
	fio();
	cin>>n>>(s+1);
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	solve(1);
	//~ mpp[0]++;
	cout<<cev<<endl;
	return 0;
}

Compilation message (stderr)

zagrade.cpp:160:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60