oj.uz

Submission #26326

# Submission time Handle Problem Language Result Execution time Memory
26326 2017-06-29T08:15:46 Z 까제비(#1110) Zagrade (COI17_zagrade) C++14
100 / 100
 1069 ms 914580 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 309 ms 832512 KB Output is correct
2 Correct 249 ms 832512 KB Output is correct
3 Correct 306 ms 832512 KB Output is correct
4 Correct 309 ms 832512 KB Output is correct
5 Correct 309 ms 832512 KB Output is correct
6 Correct 293 ms 832512 KB Output is correct
7 Correct 293 ms 832512 KB Output is correct
8 Correct 293 ms 832512 KB Output is correct
9 Correct 296 ms 832512 KB Output is correct
10 Correct 306 ms 832512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 914488 KB Output is correct
2 Correct 603 ms 914476 KB Output is correct
3 Correct 513 ms 914484 KB Output is correct
4 Correct 556 ms 914580 KB Output is correct
5 Correct 623 ms 914476 KB Output is correct
6 Correct 539 ms 914580 KB Output is correct
7 Correct 466 ms 914484 KB Output is correct
8 Correct 543 ms 914580 KB Output is correct
9 Correct 546 ms 914484 KB Output is correct
10 Correct 576 ms 914464 KB Output is correct
11 Correct 516 ms 914488 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 832512 KB Output is correct
2 Correct 249 ms 832512 KB Output is correct
3 Correct 306 ms 832512 KB Output is correct
4 Correct 309 ms 832512 KB Output is correct
5 Correct 309 ms 832512 KB Output is correct
6 Correct 293 ms 832512 KB Output is correct
7 Correct 293 ms 832512 KB Output is correct
8 Correct 293 ms 832512 KB Output is correct
9 Correct 296 ms 832512 KB Output is correct
10 Correct 306 ms 832512 KB Output is correct
11 Correct 539 ms 914488 KB Output is correct
12 Correct 603 ms 914476 KB Output is correct
13 Correct 513 ms 914484 KB Output is correct
14 Correct 556 ms 914580 KB Output is correct
15 Correct 623 ms 914476 KB Output is correct
16 Correct 539 ms 914580 KB Output is correct
17 Correct 466 ms 914484 KB Output is correct
18 Correct 543 ms 914580 KB Output is correct
19 Correct 546 ms 914484 KB Output is correct
20 Correct 576 ms 914464 KB Output is correct
21 Correct 516 ms 914488 KB Output is correct
22 Correct 873 ms 844636 KB Output is correct
23 Correct 1069 ms 844792 KB Output is correct
24 Correct 936 ms 844812 KB Output is correct
25 Correct 996 ms 844660 KB Output is correct
26 Correct 679 ms 874152 KB Output is correct
27 Correct 676 ms 860828 KB Output is correct
28 Correct 709 ms 855224 KB Output is correct
29 Correct 596 ms 914468 KB Output is correct
30 Correct 493 ms 914468 KB Output is correct
31 Correct 583 ms 846436 KB Output is correct
32 Correct 699 ms 914484 KB Output is correct