oj.uz

Submission #20984

# Submission time Handle Problem Language Result Execution time Memory
20984 2017-03-26T07:11:14 Z gs14004 Zagrade (COI17_zagrade) C++11
100 / 100
 1479 ms 44600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

int n;
char a[300005];
int sz[300005], msz[300005], vis[300005];
vector<int> gph[300005];
vector<int> dfn;

void dfs(int x, int p){
	dfn.push_back(x);
	sz[x] = 1;
	msz[x] = 0;
	for(auto &i : gph[x]){
		if(vis[i] || i == p) continue;
		dfs(i, x);
		msz[x] = max(msz[x], sz[i]);
		sz[x] += sz[i];
	}
}

int get_center(int x){
	dfn.clear();
	dfs(x, -1);
	int cur = 1e9;
	int ret = -1;
	for(auto &i : dfn){
		int w = max(msz[i], (int)dfn.size() - sz[i]);
		if(cur > w){
			cur = w;
			ret = i;
		}
	}
	return ret;
}

void dfs2(int x, int p, vector<int> &v, int dep, int mdep){
	if(a[x] == '(') dep++;
	else dep--;
	mdep = max(mdep, dep);
	if(mdep == dep) v.push_back(dep);
	for(auto &i : gph[x]){
		if(!vis[i] && i != p) dfs2(i, x, v, dep, mdep);
	}
}

void dfs3(int x, int p, vector<int> &v, int dep, int mdep){
	if(a[x] == '(') dep--;
	else dep++;
	mdep = max(mdep, dep);
	if(mdep == dep) v.push_back(dep);
	for(auto &i : gph[x]){
		if(!vis[i] && i != p) dfs3(i, x, v, dep, mdep);
	}
}

int cnt[300005];

lint getp(int x, vector<int> &l, vector<int> &r){
	lint ans = 0;
	for(auto &i : r) cnt[i]++;
	for(auto &i : l) ans += cnt[i];
	for(auto &i : r) cnt[i]--;
	return ans;
}

lint solve(int x){
	vector<int> l, r;
	lint sum = 0;
	int flg = (a[x] == '(' ? -1 : 1);
	for(auto &i : gph[x]){
		if(vis[i]) continue;
		vector<int> tl, tr;
		dfs2(i, x, tl, 0, 0);
		dfs3(i, x, tr, flg, max(flg, 0));
		for(auto &i : tl){
			l.push_back(i);
			if(flg == i) sum++;
		}
		for(auto &i : tr){
			r.push_back(i);
			if(i == 0) sum++;
		}
		sum -= getp(flg, tl, tr);
	}
	sum += getp(flg, l, r);
	return sum;
}

int main(){
	scanf("%d %s",&n,a+1);
	for(int i=1; i<n; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	queue<int> que;
	que.push(1);
	lint ans = 0;
	while(!que.empty()){
		int x = que.front();
		que.pop();
		x = get_center(x);
		ans += solve(x);
		vis[x] = 1;
		for(auto &i : gph[x]){
			if(!vis[i]) que.push(i);
		}
	}
	cout << ans;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:93:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s",&n,a+1);
                       ^
zagrade.cpp:96:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14036 KB Output is correct
2 Correct 3 ms 14036 KB Output is correct
3 Correct 0 ms 14036 KB Output is correct
4 Correct 3 ms 14036 KB Output is correct
5 Correct 6 ms 14036 KB Output is correct
6 Correct 3 ms 14036 KB Output is correct
7 Correct 3 ms 14036 KB Output is correct
8 Correct 3 ms 14036 KB Output is correct
9 Correct 3 ms 14036 KB Output is correct
10 Correct 0 ms 14036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 40004 KB Output is correct
2 Correct 539 ms 42040 KB Output is correct
3 Correct 499 ms 40008 KB Output is correct
4 Correct 479 ms 41524 KB Output is correct
5 Correct 489 ms 40008 KB Output is correct
6 Correct 519 ms 40760 KB Output is correct
7 Correct 523 ms 40004 KB Output is correct
8 Correct 479 ms 40884 KB Output is correct
9 Correct 496 ms 40004 KB Output is correct
10 Correct 446 ms 44600 KB Output is correct
11 Correct 483 ms 44088 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14036 KB Output is correct
2 Correct 3 ms 14036 KB Output is correct
3 Correct 0 ms 14036 KB Output is correct
4 Correct 3 ms 14036 KB Output is correct
5 Correct 6 ms 14036 KB Output is correct
6 Correct 3 ms 14036 KB Output is correct
7 Correct 3 ms 14036 KB Output is correct
8 Correct 3 ms 14036 KB Output is correct
9 Correct 3 ms 14036 KB Output is correct
10 Correct 0 ms 14036 KB Output is correct
11 Correct 533 ms 40004 KB Output is correct
12 Correct 539 ms 42040 KB Output is correct
13 Correct 499 ms 40008 KB Output is correct
14 Correct 479 ms 41524 KB Output is correct
15 Correct 489 ms 40008 KB Output is correct
16 Correct 519 ms 40760 KB Output is correct
17 Correct 523 ms 40004 KB Output is correct
18 Correct 479 ms 40884 KB Output is correct
19 Correct 496 ms 40004 KB Output is correct
20 Correct 446 ms 44600 KB Output is correct
21 Correct 483 ms 44088 KB Output is correct
22 Correct 1479 ms 27276 KB Output is correct
23 Correct 1463 ms 27280 KB Output is correct
24 Correct 1456 ms 27340 KB Output is correct
25 Correct 1399 ms 27440 KB Output is correct
26 Correct 643 ms 31160 KB Output is correct
27 Correct 689 ms 29060 KB Output is correct
28 Correct 739 ms 28260 KB Output is correct
29 Correct 496 ms 44596 KB Output is correct
30 Correct 506 ms 44596 KB Output is correct
31 Correct 106 ms 31692 KB Output is correct
32 Correct 519 ms 44084 KB Output is correct