oj.uz

Submission #41766

# Submission time Handle Problem Language Result Execution time Memory
41766 2018-02-21T07:52:30 Z top34051 Zagrade (COI17_zagrade) C++14
10 / 100
 3000 ms 46584 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;
		}
	}
	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 'void decom(int)':
zagrade.cpp:64:2: warning: label 'redo' defined but not used [-Wunused-label]
  redo:
  ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:88:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d",ans);
                 ^
zagrade.cpp:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
zagrade.cpp:82: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:84: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 7416 KB Output is correct
2 Correct 9 ms 7668 KB Output is correct
3 Correct 9 ms 7748 KB Output is correct
4 Correct 9 ms 7748 KB Output is correct
5 Correct 9 ms 7808 KB Output is correct
6 Correct 8 ms 7880 KB Output is correct
7 Correct 9 ms 7928 KB Output is correct
8 Correct 9 ms 7956 KB Output is correct
9 Correct 8 ms 7956 KB Output is correct
10 Correct 8 ms 7956 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 ms 46584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7668 KB Output is correct
3 Correct 9 ms 7748 KB Output is correct
4 Correct 9 ms 7748 KB Output is correct
5 Correct 9 ms 7808 KB Output is correct
6 Correct 8 ms 7880 KB Output is correct
7 Correct 9 ms 7928 KB Output is correct
8 Correct 9 ms 7956 KB Output is correct
9 Correct 8 ms 7956 KB Output is correct
10 Correct 8 ms 7956 KB Output is correct
11 Execution timed out 3016 ms 46584 KB Time limit exceeded
12 Halted 0 ms 0 KB -