提出 #485282

---

ソースコード 拡げる

#include<cstdio>
#include<unordered_map>
#include<vector>
#define N 100100
using namespace std;
long long ans=0;
unordered_map<int,long long> neg[N],pos[N];
vector<int> g[N];
int f[N],add_pos[N],add_neg[N];
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
char s[N];
bool vis[N];
inline long long get_val(unordered_map<int,long long> &m,int v){
	return m.count(v)?m[v]:0;
}
void DFS(int u){
	vis[u]=true;
	int mc,mv=0,tmp;
	bool leaf=true;
	vector<int> ch;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v]) continue;
		DFS(v);
		ch.push_back(v);
		if((tmp=pos[find(v)].size()+neg[find(v)].size())>mv){
			mc=v;
			mv=tmp;
		}
		leaf=false;
	}
	if(leaf){
		if(s[u]=='('){
			pos[u][1]++;
		}
		else{
			neg[u][1]++;
		}
		f[u]=u;
		return;
	}
	f[u]=find(mc);
	int p=f[u];
	for(int i=0;i<ch.size();i++){
		int c=ch[i];
		if(c==mc) continue;
		c=find(c);
		for(auto it=pos[c].begin();it!=pos[c].end();++it){
			int tmp=it->first+add_pos[c];
			if(s[u]=='(') tmp++;
			else tmp--;
			if(tmp<0) continue;
			ans+=it->second*get_val(neg[p],tmp-add_neg[p]);
		}
		for(auto it=neg[c].begin();it!=neg[c].end();++it){
			int tmp=it->first+add_neg[c];
			if(s[u]=='(') tmp--;
			else tmp++;
			if(tmp<0) continue;
			ans+=it->second*get_val(pos[p],tmp-add_pos[p]);
		}
		for(auto it=pos[c].begin();it!=pos[c].end();++it){
			pos[p][it->first+add_pos[c]-add_pos[p]]+=it->second;
		}
		pos[c].clear();
		for(auto it=neg[c].begin();it!=neg[c].end();++it){
			neg[p][it->first+add_neg[c]-add_neg[p]]+=it->second;
		}
		neg[c].clear();
	}
	pos[p][0-add_pos[p]]++;
	neg[p][0-add_neg[p]]++;
	if(s[u]=='(') add_pos[p]++,add_neg[p]--;
	else add_pos[p]--,add_neg[p]++;
	auto it=pos[p].find(-1-add_pos[p]);
	if(it!=pos[p].end()) pos[p].erase(it);
	it=neg[p].find(-1-add_neg[p]);
	if(it!=neg[p].end()) neg[p].erase(it);
	ans+=get_val(pos[p],-add_pos[p]);
	ans+=get_val(neg[p],-add_neg[p]);
}
int main(){
	int n,x,y;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	DFS(1);
	printf("%lld\n",ans);
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:88:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
                 ^
./Main.cpp:90:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

ジャッジ結果