oj.uz

Submission #250864

# Submission time Handle Problem Language Result Execution time Memory
250864 2020-07-19T10:19:27 Z VEGAnn Zagrade (COI17_zagrade) C++14
0 / 100
 3000 ms 26636 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 300100;
vector<int> g[N];
int ad[N], n, ans = 0;
string s;

void dfs(int v, int p, int sm){
    if (sm < 0) return;

    if (sm == 0)
        ans++;

    for (int u : g[v]){
        if (p == u) continue;

        dfs(u, v, sm + ad[v]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> s;

    for (int i = 0; i < n; i++)
        ad[i] = (s[i] == '(' ? 1 : -1);

    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    for (int i = 0; i < n; i++)
        dfs(i, -1, ad[i]);

    cout << ans;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -