oj.uz

Submission #26321

# Submission time Handle Problem Language Result Execution time Memory
26321 2017-06-29T08:03:20 Z 까제비(#1110) Zagrade (COI17_zagrade) C++14
30 / 100
 546 ms 900516 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];
				}
				Dy[0][ix][s] += Dy[0][nix][s];
			}
			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];
				}
				Dy[1][ix][s] += Dy[1][nix][s];
			}
		}

		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();
				if(SZ(Dy[k][ix]) == 0)
					Dy[k][ix].push_front(0);
			}
			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:73:8: warning: unused variable 'n' [-Wunused-variable]
    int n = Sz[w], nix = DyIx[w];
        ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:107: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:109: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 832640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 900424 KB Output is correct
2 Correct 509 ms 900404 KB Output is correct
3 Correct 486 ms 900420 KB Output is correct
4 Correct 506 ms 900516 KB Output is correct
5 Correct 523 ms 900408 KB Output is correct
6 Correct 516 ms 900516 KB Output is correct
7 Correct 533 ms 900416 KB Output is correct
8 Correct 526 ms 900512 KB Output is correct
9 Correct 546 ms 900412 KB Output is correct
10 Correct 519 ms 900396 KB Output is correct
11 Correct 536 ms 900424 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 832640 KB Output isn't correct
2 Halted 0 ms 0 KB -