oj.uz

Submission #26350

# Submission time Handle Problem Language Result Execution time Memory
26350 2017-06-29T10:00:11 Z kajebiii Zagrade (COI17_zagrade) C++14
100 / 100
 993 ms 914584 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 832512 KB Output is correct
2 Correct 259 ms 832512 KB Output is correct
3 Correct 296 ms 832512 KB Output is correct
4 Correct 273 ms 832512 KB Output is correct
5 Correct 319 ms 832512 KB Output is correct
6 Correct 293 ms 832512 KB Output is correct
7 Correct 256 ms 832512 KB Output is correct
8 Correct 309 ms 832512 KB Output is correct
9 Correct 256 ms 832512 KB Output is correct
10 Correct 299 ms 832512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 914492 KB Output is correct
2 Correct 566 ms 914472 KB Output is correct
3 Correct 619 ms 914484 KB Output is correct
4 Correct 529 ms 914584 KB Output is correct
5 Correct 533 ms 914480 KB Output is correct
6 Correct 503 ms 914580 KB Output is correct
7 Correct 549 ms 914484 KB Output is correct
8 Correct 549 ms 914580 KB Output is correct
9 Correct 493 ms 914484 KB Output is correct
10 Correct 539 ms 914464 KB Output is correct
11 Correct 536 ms 914488 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 832512 KB Output is correct
2 Correct 259 ms 832512 KB Output is correct
3 Correct 296 ms 832512 KB Output is correct
4 Correct 273 ms 832512 KB Output is correct
5 Correct 319 ms 832512 KB Output is correct
6 Correct 293 ms 832512 KB Output is correct
7 Correct 256 ms 832512 KB Output is correct
8 Correct 309 ms 832512 KB Output is correct
9 Correct 256 ms 832512 KB Output is correct
10 Correct 299 ms 832512 KB Output is correct
11 Correct 539 ms 914492 KB Output is correct
12 Correct 566 ms 914472 KB Output is correct
13 Correct 619 ms 914484 KB Output is correct
14 Correct 529 ms 914584 KB Output is correct
15 Correct 533 ms 914480 KB Output is correct
16 Correct 503 ms 914580 KB Output is correct
17 Correct 549 ms 914484 KB Output is correct
18 Correct 549 ms 914580 KB Output is correct
19 Correct 493 ms 914484 KB Output is correct
20 Correct 539 ms 914464 KB Output is correct
21 Correct 536 ms 914488 KB Output is correct
22 Correct 916 ms 844636 KB Output is correct
23 Correct 943 ms 844792 KB Output is correct
24 Correct 896 ms 844812 KB Output is correct
25 Correct 993 ms 844660 KB Output is correct
26 Correct 676 ms 874148 KB Output is correct
27 Correct 699 ms 860828 KB Output is correct
28 Correct 639 ms 855224 KB Output is correct
29 Correct 526 ms 914468 KB Output is correct
30 Correct 563 ms 914472 KB Output is correct
31 Correct 653 ms 846436 KB Output is correct
32 Correct 543 ms 914484 KB Output is correct