oj.uz

Submission #41767

# Submission time Handle Problem Language Result Execution time Memory
41767 2018-02-21T07:53:54 Z top34051 Zagrade (COI17_zagrade) C++14
10 / 100
 573 ms 82100 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
const int maxn = 3e5 + 5;

int n;
char s[maxn];
int sz[maxn], cen[maxn];
vector<int> way[maxn];

long long ans;
int cnt[2][maxn];

void dfs(int t, int u, int last, int cur, int mx, vector<int> &vec) {
	if(t==0) cur += s[u]=='(' ? 1 : -1;
	else cur += s[u]=='(' ? -1 : 1;
	mx = max(mx, cur);
	if(cur==mx) vec.pb(cur);
	for(auto v : way[u]) {
		if(v==last || cen[v]) continue;
		dfs(t,v,u,cur,mx,vec);
	}
}

void solve(int u) {
	int t = s[u]=='(' ? -1 : 1;
	vector<int> L, R;
	for(auto v : way[u]) {
		if(cen[v]) continue;
		vector<int> tl, tr;
		dfs(0,v,u,0,0,tl);
		dfs(1,v,u,t,max(t,0),tr);
		for(auto x : tl) {
			L.push_back(x);
			ans += cnt[1][x];
			if(x==t) ans++;
		}
		for(auto x : tr) {
			R.push_back(x);
			ans += cnt[0][x];
			if(x==0) ans++;
		}
		for(auto x : tl) cnt[0][x]++;
		for(auto x : tr) cnt[1][x]++;
	}
	for(auto x : L) cnt[0][x]--;
	for(auto x : R) cnt[1][x]--;
}

void survey(int u, int last) {
//    printf("survey %d %d\n",u,last);
	sz[u] = 1;
	for(auto v : way[u]) {
		if(v==last || cen[v]) continue;
		survey(v, u);
		sz[u] += sz[v];
	}
}

void decom(int u) {
	survey(u, 0);
	int x = u, last = 0;
	redo:
	for(auto v : way[x]) {
		if(v==last || cen[v]) continue;
		if(sz[v]>sz[u]/2) {
			last = x; x = v;
			goto redo;
		}
	}
	solve(x);
	cen[x] = 1;
	for(auto v : way[x]) {
		if(cen[v]) continue;
		decom(v);
	}
}

int main() {
    int x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
	for(int i=0;i<n-1;i++) {
		scanf("%d%d",&x,&y);
		way[x].pb(y); way[y].pb(x);
	}
	decom(1);
	printf("%d",ans);
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:89:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d",ans);
                 ^
zagrade.cpp:82:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
zagrade.cpp:83:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
                                          ^
zagrade.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7608 KB Output is correct
7 Correct 8 ms 7608 KB Output is correct
8 Correct 9 ms 7644 KB Output is correct
9 Correct 9 ms 7644 KB Output is correct
10 Correct 8 ms 7648 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 38504 KB Output is correct
2 Correct 564 ms 44156 KB Output is correct
3 Correct 536 ms 47152 KB Output is correct
4 Correct 552 ms 52480 KB Output is correct
5 Correct 486 ms 55472 KB Output is correct
6 Correct 511 ms 60148 KB Output is correct
7 Correct 529 ms 63712 KB Output is correct
8 Correct 556 ms 68904 KB Output is correct
9 Correct 495 ms 72260 KB Output is correct
10 Correct 526 ms 79076 KB Output is correct
11 Incorrect 573 ms 82100 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7420 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7608 KB Output is correct
7 Correct 8 ms 7608 KB Output is correct
8 Correct 9 ms 7644 KB Output is correct
9 Correct 9 ms 7644 KB Output is correct
10 Correct 8 ms 7648 KB Output is correct
11 Correct 496 ms 38504 KB Output is correct
12 Correct 564 ms 44156 KB Output is correct
13 Correct 536 ms 47152 KB Output is correct
14 Correct 552 ms 52480 KB Output is correct
15 Correct 486 ms 55472 KB Output is correct
16 Correct 511 ms 60148 KB Output is correct
17 Correct 529 ms 63712 KB Output is correct
18 Correct 556 ms 68904 KB Output is correct
19 Correct 495 ms 72260 KB Output is correct
20 Correct 526 ms 79076 KB Output is correct
21 Incorrect 573 ms 82100 KB Output isn't correct