Submission #370059

#	Time	Username	Problem	Language	Result	Execution time	Memory
370059		AriaH	Zagrade (COI17_zagrade)	C++11	100 / 100	1214 ms	92484 KiB

zagrade

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

char C[N];

int n, A[N], hide[N], sub[N];

pii St[N], Fi[N]; /// St[v].F -> min prefix sum chie   St[v].S -> sum chie

ll tot, cnt[N];

vector < int > G[N];

vector < int > subtree[N];

void dfs(int v, int P)
{
	subtree[v].clear();
	sub[v] = 1;
	for(auto u : G[v])
	{
		if(u == P || hide[u]) continue;
		dfs(u, v);
		sub[v] += sub[u];
	}
}

int find(int v, int P, int _n)
{
	for(auto u : G[v])
	{
		if(u == P || hide[u]) continue;
		if(sub[u] * 2 > _n) return find(u, v, _n);
	}
	return v;
}

void calc(int v, int P)
{
	St[v].S = St[P].S + A[v];
	St[v].F = min(St[P].F + A[v], A[v]);
	if(St[v].F >= 0)
	{
		cnt[St[v].S] ++;
	}
	for(auto u : G[v])
	{
		if(u == P || hide[u]) continue;
		calc(u, v);
	}
}

void calc2(int v, int P, int root)
{
	subtree[root].push_back(v);
	Fi[v].S = Fi[P].S + A[v];
	Fi[v].F = min(Fi[P].F, Fi[v].S);
	for(auto u : G[v])
	{
		if(u == P || hide[u]) continue;
		calc2(u, v, root);
	}
}

void dec(int v)
{
	dfs(v, 0);
	int _n = sub[v], centroid = find(v, 0, _n);
	///printf("centroid = %d size = %d\n", centroid, _n);
	St[0] = Mp(0, 0);
	Fi[centroid] = Mp(0, 0);
	for(int i = 0; i <= _n; i ++) cnt[i] = 0;
	calc(centroid, 0);
	for(auto u : G[centroid])
	{
		if(hide[u]) continue;
		calc2(u, centroid, u);
		for(auto cu : subtree[u])
		{
			if(St[cu].F >= 0)
			{
				cnt[St[cu].S] --;
			}
		}
		for(auto cu : subtree[u])
		{
			if(Fi[cu].F == Fi[cu].S)
			{
				tot += cnt[-Fi[cu].F];
			}
		}
		for(auto cu : subtree[u])
		{
			if(St[cu].F >= 0)
			{
				cnt[St[cu].S] ++;
			}
		}
	}
	hide[centroid] = 1;
	tot += cnt[0];
	for(auto u : G[centroid])
	{
		if(hide[u]) continue;
		dec(u);
	}
}

int main()
{
	scanf("%d%s", &n, C);
	for(int i = 0; i < n; i ++)
	{
		A[i + 1] = (C[i] == '('? 1 : -1);
	}
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dec(1);
	printf("%lld", tot);
    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |  scanf("%d%s", &n, C);
      |  ~~~~~^~~~~~~~~~~~~~~
zagrade.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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