oj.uz

Submission #350155

# Submission time Handle Problem Language Result Execution time Memory
350155 2021-01-19T03:27:33 Z arnold518 Zagrade (COI17_zagrade) C++14
10 / 100
 834 ms 48352 KB 
#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("%d\n", ans/2);
}

Compilation message

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:223:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
  223 |  printf("%d\n", ans/2);
      |          ~^     ~~~~~
      |           |        |
      |           int      ll {aka long long int}
      |          %lld
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7404 KB Output is correct
2 Correct 7 ms 7404 KB Output is correct
3 Correct 7 ms 7532 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 7 ms 7404 KB Output is correct
6 Correct 7 ms 7404 KB Output is correct
7 Correct 8 ms 7404 KB Output is correct
8 Correct 7 ms 7404 KB Output is correct
9 Correct 7 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 47132 KB Output is correct
2 Correct 788 ms 48224 KB Output is correct
3 Correct 827 ms 47340 KB Output is correct
4 Correct 818 ms 47968 KB Output is correct
5 Correct 826 ms 47212 KB Output is correct
6 Correct 810 ms 47736 KB Output is correct
7 Correct 804 ms 47084 KB Output is correct
8 Correct 816 ms 47648 KB Output is correct
9 Correct 809 ms 47256 KB Output is correct
10 Correct 708 ms 48352 KB Output is correct
11 Incorrect 689 ms 47840 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7404 KB Output is correct
2 Correct 7 ms 7404 KB Output is correct
3 Correct 7 ms 7532 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 7 ms 7404 KB Output is correct
6 Correct 7 ms 7404 KB Output is correct
7 Correct 8 ms 7404 KB Output is correct
8 Correct 7 ms 7404 KB Output is correct
9 Correct 7 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 834 ms 47132 KB Output is correct
12 Correct 788 ms 48224 KB Output is correct
13 Correct 827 ms 47340 KB Output is correct
14 Correct 818 ms 47968 KB Output is correct
15 Correct 826 ms 47212 KB Output is correct
16 Correct 810 ms 47736 KB Output is correct
17 Correct 804 ms 47084 KB Output is correct
18 Correct 816 ms 47648 KB Output is correct
19 Correct 809 ms 47256 KB Output is correct
20 Correct 708 ms 48352 KB Output is correct
21 Incorrect 689 ms 47840 KB Output isn't correct