Submission #350157

#	Time	Username	Problem	Language	Result	Execution time	Memory
350157		arnold518	Zagrade (COI17_zagrade)	C++14	100 / 100	2047 ms	48480 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N;
char S[MAXN+10];
vector<int> adj[MAXN+10];

int sz[MAXN+10], del[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		getsz(nxt, now);
		sz[now]+=sz[nxt];
	}
}

int getcen(int now, int bef, int S)
{
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		if(sz[nxt]>S/2) return getcen(nxt, now, S);
	}
	return now;
}

vector<int> V;
int cnt[MAXN+10];
ll ans=0;

void dfs(int now, int bef, int p, int q)
{
	if(S[now]=='(') p++;
	else
	{
		p--;
		q=min(q, p);
	}
	if(p==q)
	{
		//printf("%d : %d %d\n", now, p, cnt[p+N]);
		ans+=cnt[p+N];
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		dfs(nxt, now, p, q);
	}
}

void dfs2(int now, int bef, int p, int q)
{
	if(S[now]==')') p++;
	else
	{
		p--;
		q=min(q, p);
	}
	if(p==q)
	{
		V.push_back(p+N);
		cnt[p+N]++;
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		dfs2(nxt, now, p, q);
	}
}

void dfs3(int now, int bef, int p, int q)
{
	if(S[now]==')') p++;
	else
	{
		p--;
		q=min(q, p);
	}
	if(p==q)
	{
		//printf("%d : %d %d\n", now, p, cnt[p+N]);
		ans+=cnt[p+N];
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		dfs3(nxt, now, p, q);
	}
}

void dfs4(int now, int bef, int p, int q)
{
	if(S[now]=='(') p++;
	else
	{
		p--;
		q=min(q, p);
	}
	if(p==q)
	{
		V.push_back(p+N);
		cnt[p+N]++;
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		dfs4(nxt, now, p, q);
	}
}

void decomp(int now)
{
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	del[now]=true;

	//printf("CEN %d\n", now);

	{
		int p=0, q=0;
		if(S[now]=='(') p++;
		else
		{
			p--;
			q=min(q, p);
		}

		V.push_back(0+N);
		cnt[0+N]++;
		for(int i=0; i<adj[now].size(); i++)
		{
			int nxt=adj[now][i];
			if(del[nxt]) continue;
			dfs(nxt, now, p, q);
			dfs2(nxt, now, 0, 0);
		}
		for(auto it : V) cnt[it]=0;
		V.clear();

		V.push_back(0+N);
		cnt[0+N]++;
		for(int i=adj[now].size()-1; i>=0; i--)
		{
			int nxt=adj[now][i];
			if(del[nxt]) continue;
			dfs(nxt, now, p, q);
			dfs2(nxt, now, 0, 0);
		}
		for(auto it : V) cnt[it]=0;
		V.clear();
	}

	{
		int p=0, q=0;
		if(S[now]==')') p++;
		else
		{
			p--;
			q=min(q, p);
		}

		V.push_back(0+N);
		cnt[0+N]++;
		for(int i=0; i<adj[now].size(); i++)
		{
			int nxt=adj[now][i];
			if(del[nxt]) continue;
			dfs3(nxt, now, p, q);
			dfs4(nxt, now, 0, 0);
		}
		for(auto it : V) cnt[it]=0;
		V.clear();

		V.push_back(0+N);
		cnt[0+N]++;
		for(int i=adj[now].size()-1; i>=0; i--)
		{
			int nxt=adj[now][i];
			if(del[nxt]) continue;
			dfs3(nxt, now, p, q);
			dfs4(nxt, now, 0, 0);
		}
		for(auto it : V) cnt[it]=0;
		V.clear();
	}

	for(int nxt : adj[now])
	{
		if(del[nxt]) continue;
		decomp(nxt);
	}
}

int main()
{
	scanf("%d", &N);
	scanf(" %s", S+1);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	decomp(1);
	printf("%lld\n", ans/2);
}

Compilation message (stderr)

zagrade.cpp: In function 'void decomp(int)':
zagrade.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i=0; i<adj[now].size(); i++)
      |                ~^~~~~~~~~~~~~~~~
zagrade.cpp:180:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |   for(int i=0; i<adj[now].size(); i++)
      |                ~^~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:212:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  212 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
zagrade.cpp:213:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  213 |  scanf(" %s", S+1);
      |  ~~~~~^~~~~~~~~~~~
zagrade.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  217 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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