Submission #26350

#	Time	Username	Problem	Language	Result	Execution time	Memory
26350		kajebiii	Zagrade (COI17_zagrade)	C++14	100 / 100	993 ms	914584 KiB

zagrade

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 6e5 + 100;

/*
ll Ans = 0; int Lv[MAX_N];
void subtask() {
for(int i=0; i<MAX_N; i++) Lv[i] = 0;
int lv = MAX_N/2;
for(int i=0; i<N; i++) {
if(S[i] == '(') {
Lv[lv]++;
lv++;
} else {
Lv[lv] = 0;
lv--;
Ans += Lv[lv];
}
}
}
*/
int N; char S[MAX_N];
vector<int> Ed[MAX_N];
int lv[2] ={MAX_N/2, MAX_N/2};
int Lv[2][MAX_N];
int Sz[MAX_N];
ll Ans = 0;
deque<int> Dy[2][MAX_N]; int DyIx[MAX_N], DN;
void dfs(int v, int p) {
	Sz[v] = 1;
	int maxV = -1, wx = -1;
	for(int w : Ed[v]) if(w != p) {
		dfs(w, v);
		Sz[v] += Sz[w];
		if(maxV < Sz[w]) {
			maxV = Sz[w];
			wx = w;
		}
	}
	char s[5] = "()";
	int ix = -1;
	if(wx == -1) {
		ix = DyIx[v] = DN; DN++;
		for(int k=0; k<2; k++) {
			while(SZ(Dy[k][ix]) <= Sz[v]) Dy[k][ix].push_back(0);
			if(S[v] == s[k]) Dy[k][ix][1]++;
		}
	} else {
		ix = DyIx[v] = DyIx[wx];


		for(int k=0; k<2; k++)
			if(S[v] == s[k])
				Dy[k][ix][0]++;

		if(S[v] == '(') Ans += Dy[1][ix][1];
		if(S[v] == ')') Ans += Dy[0][ix][1];
		//		printf("[%d : Ans : %lld]\n", v, Ans);

		for(int w : Ed[v]) if(w != p && w != wx) {
			int n = Sz[w], nix = DyIx[w];
			for(int s=0; s<=Sz[w]; s++) {
				int st = s + 1;
				if(S[v] == ')') st -= 2;
				if(st >= 0 && st < SZ(Dy[0][ix])) {
					Ans += 1ll * Dy[0][nix][s] * Dy[1][ix][st];
				}
			}
			for(int s=0; s<=Sz[w]; s++) {
				int st = s + 1;
				if(S[v] == '(') st -= 2;
				if(st >= 0 && st < SZ(Dy[0][ix])) {
					Ans += 1ll * Dy[1][nix][s] * Dy[0][ix][st];
				}
			}
			for(int s=0; s<=Sz[w]; s++) {
				Dy[0][ix][s] += Dy[0][nix][s];
				Dy[1][ix][s] += Dy[1][nix][s];
			}
			Dy[0][nix].clear(); Dy[0][nix].shrink_to_fit();
			Dy[1][nix].clear(); Dy[1][nix].shrink_to_fit();
		}

		for(int k=0; k<2; k++) {
			if(S[v] == s[k]) {
				//				Dy[k][ix][0]++;
				Dy[k][ix].push_front(0);
			} else {
				Dy[k][ix].pop_front();
			}
			while(SZ(Dy[k][ix]) <= Sz[v]) Dy[k][ix].push_back(0);
		}
	}
	//	printf("[%d finish]\n", v);for(int k=0; k<2; k++) {printf("Dy (%d)\n", k);for(int x : Dy[k][ix]) printf("[%d]", x); puts("");}puts("");
}
int main() {
	cin >> N; scanf("%s", S+1);
	REP(i, N-1) {
		int x, y; scanf("%d%d", &x, &y);
		Ed[x].push_back(y);
		Ed[y].push_back(x);
	}
	dfs(1, 0);
	printf("%lld\n", Ans);
	return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'void dfs(int, int)':
zagrade.cpp:74:8: warning: unused variable 'n' [-Wunused-variable]
    int n = Sz[w], nix = DyIx[w];
        ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:110:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin >> N; scanf("%s", S+1);
                            ^
zagrade.cpp:112:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

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