Submission #931642

#	Time	Username	Problem	Language	Result	Execution time	Memory
931642		vjudge1	Zagrade (COI17_zagrade)	C++17	0 / 100	46 ms	11492 KiB

zagrade

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60