oj.uz

Submission #104555

# Submission time Handle Problem Language Result Execution time Memory
104555 2019-04-07T22:52:50 Z Shtef Zagrade (COI17_zagrade) C++14
10 / 100
 3000 ms 29916 KB 
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;

int n, val[300005], ss[300005], br;
ll dp[300005], sol;
char s[300005];
vector <int> ms[300005];
bool bio[300005];

inline void dfs1(int x, int p){
	br++;
	ss[x] = 1;
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		dfs1(o, x);
		ss[x] += ss[o];
	}
}

inline int dfs2(int x, int p){
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		if(ss[o] > br / 2)
			return dfs2(o, x);
	}
	return x;
}

inline void processdp(int x, int p, int sad, int sve, int add){
	sad = (val[x] == 1 ? max(1, sad + 1) : sad - 1);
	sve -= (sad < 0);
	if(sad <= 0){
		dp[-sve] += add;
	}
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		processdp(o, x, sad, sve, add);
	}
}

inline void dfs3(int x, int p, int sad, int sve){
	sad = (val[x] == -1 ? min(-1, sad - 1) : sad + 1);
	sve += (sad > 0);
	if(sad >= 0){
		sol += dp[sve];
	}
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		dfs3(o, x, sad, sve);
	}
}

inline void decompose(int root){
	dfs1(root, -1);
	int centroid = dfs2(root, -1);
	bio[centroid] = 1;
	processdp(centroid, -1, 0, 0, 1);
	sol += dp[0];
	for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		int o = *i;
		if(bio[o])
			continue;
		processdp(o, centroid, val[centroid], min(0, val[centroid]), -1);
		dfs3(o, centroid, 0, 0);
		processdp(o, centroid, val[centroid], min(0, val[centroid]), 1);
	}
	//cout << centroid << ' ' << sol << endl;
	processdp(centroid, -1, 0, 0, -1);
	for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		int o = *i;
		if(bio[o])
			continue;
		decompose(o);
	}
}

int main(){
scanf("%d", &n);
scanf("%s", &s);
for(int i = 0 ; i < n ; ++i){
	if(s[i] == '('){
		val[i + 1] = 1;
	}
	else{
		val[i + 1] = -1;
	}
}
for(int i = 0 ; i < n - 1 ; ++i){
	int x, y;
	scanf("%d %d", &x, &y);
	ms[x].push_back(y);
	ms[y].push_back(x);
}
decompose(1);
printf("%lld\n", sol);

return 0;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:92:15: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
 scanf("%s", &s);
             ~~^
zagrade.cpp:91:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &n);
 ~~~~~^~~~~~~~~~
zagrade.cpp:92:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%s", &s);
 ~~~~~^~~~~~~~~~
zagrade.cpp:103:7: 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 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct
4 Correct 11 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 11 ms 7424 KB Output is correct
8 Correct 14 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct
4 Correct 11 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 11 ms 7424 KB Output is correct
8 Correct 14 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Execution timed out 3097 ms 29916 KB Time limit exceeded
12 Halted 0 ms 0 KB -