oj.uz

Submission #931642

# Submission time Handle Problem Language Result Execution time Memory
931642 2024-02-22T07:40:19 Z vjudge1 Zagrade (COI17_zagrade) C++17
0 / 100
 46 ms 11492 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

typedef long long ll;

const int N = 3e5 + 4;

int n, _f[8 * N], ans[N];
string s;

int& f(int k) {
    k += 2 * N;
    return _f[k];
}

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

    for (int i = 0; i < 8 * N; i++) {
        _f[i] = N;
    }

    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int v, u;
        cin >> v >> u;
    }

    int sum = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(') {
            sum--;
            f(1 + sum) = min(f(1 + sum), i);
        }
        else {
            sum++;
            f(-1 + sum) = min(f(-1 + sum), i);
        }
        
        int R = f(sum);
        if (R < n && s[i] == '(') {
            ans[i] = ans[R + 1] + 1;
        }
    }

    ll Ans = 0;
    for (int i = 0; i < n; i++) {
        Ans += ans[i];
    }
    cout << Ans;

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

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