| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 392789 |
2021-04-21T16:50:33 Z |
asbsfds |
Zagrade (COI17_zagrade) |
C++14 |
|
584 ms |
42652 KB |
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 3e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n;
char niz[maxn];
int a[maxn];
vector< int > graph[maxn];
bool bio[maxn];
int dp[maxn];
map< int, int > m;
int cal(int x, int parr) {
dp[x] = 1;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren != parr && !bio[tren]) dp[x] += cal(tren, x);
}
return dp[x];
}
int fin(int x, int parr, int siz) {
int sum = 0;
int maxi = 0;
int ind = -1;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren == parr) continue;
if (bio[tren]) continue;
sum += dp[tren];
if (dp[tren] > maxi) {
maxi = dp[tren];
ind = tren;
}
}
if (2 * maxi <= siz) return x;
return fin(ind, x, siz);
}
void update(int x, int parr, int sum, int mini) {
//printf("update: %d %d %d %d\n", x, parr, sum, mini);
sum += a[x];
mini = a[x] + min(mini, 0);
if (sum >= 0 && mini >= 0) m[sum]++;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren != parr && !bio[tren]) update(tren, x, sum, mini);
}
}
llint dfs(int x, int parr, int sum, int mini) {
//printf("dfs: %d %d %d %d\n", x, parr, sum, mini);
sum += a[x];
mini = min(mini, sum);
llint out = 0;
if (mini >= sum) out += m[-sum];
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (tren != parr && !bio[tren]) out += dfs(tren, x, sum, mini);
}
return out;
}
llint solve(int x) {
int siz = cal(x, -1);
x = fin(x, -1, siz);
//printf("solve: %d %d\n", x, siz);
llint out = 0;
m.clear();
if (a[x] == 1) m[1] = 1;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (bio[tren]) continue;
out += dfs(tren, x, a[x], a[x]);
update(tren, x, 0, inf);
}
if (a[x] == -1) out += m[1];
m.clear();
for (int i = graph[x].size() - 1; i >= 0; i--) {
int tren = graph[x][i];
if (bio[tren]) continue;
out += dfs(tren, x, a[x], a[x]);
update(tren, x, 0, inf);
}
bio[x] = true;
for (int i = 0; i < graph[x].size(); i++) {
int tren = graph[x][i];
if (!bio[tren]) out += solve(tren);
}
return out;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf(" %c", niz+i);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
a[i] = (niz[i] == '(' ? 1 : -1);
}
memset(bio, false, sizeof bio);
printf("%lld\n", solve(1));
return 0;
}
Compilation message
zagrade.cpp: In function 'int cal(int, int)':
zagrade.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int fin(int, int, int)':
zagrade.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'void update(int, int, int, int)':
zagrade.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint dfs(int, int, int, int)':
zagrade.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint solve(int)':
zagrade.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i = 0; i < graph[x].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
zagrade.cpp:116:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
116 | for (int i = 1; i <= n; i++) scanf(" %c", niz+i);
| ~~~~~^~~~~~~~~~~~~~
zagrade.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
584 ms |
42652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
