Submission #1312067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312067		plavac52431	Zagrade (COI17_zagrade)	C++20	100 / 100	724 ms	50712 KiB

zagrade

#include <bits/stdc++.h>
#define pb push_back
#define X first
#define Y second

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

struct zagrade {
    int maxpref=0, minpref=0, val=0;
};

const int MAXN = 3e5+7;
string str;
int bio[MAXN], cent[MAXN], sz[MAXN];
vector<vi> komp; map<int, int> cnt;
map<char, int> mapa = {{'(', 1}, {')', -1}};

zagrade zag[MAXN];
vi sus[MAXN];
int br = 1, centroid, n;
ll sol = 0;

void dfs2(int x) {
    bio[x] = br; komp.back().pb(x);
    if (str[x-1] == '(') ++zag[x].val;
    else --zag[x].val;
    zag[x].minpref = min(zag[x].minpref, zag[x].val);
    zag[x].maxpref = max(zag[x].maxpref, zag[x].val);
    if (zag[x].val-zag[x].minpref <= 0) {
        ++cnt[-(zag[x].minpref)];
    }

    for (auto y: sus[x]) {
        if (bio[y] == br or cent[y] or y == x) continue;
        zag[y] = zag[x]; dfs2(y);
    }
}

void dfs(int x) {
    bio[x] = br;
    if (br > 1) sz[x] = 1;
    for (auto y: sus[x]) {
        if (cent[y] or bio[y] == br) continue;
        bio[y] = br; dfs(y);
        if (br > 1) sz[x] += sz[y];
    }
}

void nadi(int x, int cvor) {
    if (sz[x]-1 >= sz[cvor]/2) centroid = x;
    bio[x] = br;
    for (auto y: sus[x]) {
        if (cent[y] or bio[y] == br) continue;
        nadi(y, cvor);
    }
}

void centroidna(int cvor) {
    cnt = {}, komp = {};
    ++br; dfs(cvor); ++br; nadi(cvor, cvor);
    cent[centroid] = 1;
    for (auto x: sus[centroid]) {
        if (cent[x] == 0) {
            komp.push_back({}); ++br; dfs2(x);
        }
    }

    ++cnt[0]; //komp = {{7, 5, 4}, {1, 3, 6}};
    for (auto v: komp) {
        for (auto x: v) {
            if (zag[x].val-zag[x].minpref <= 0) {
                --cnt[-(zag[x].minpref)];
            }
        }
        for (auto x: v) {
            int val2 = zag[x].val+mapa[str[centroid-1]];
            int maxpf = max(0, zag[x].maxpref+mapa[str[centroid-1]]);
            if (val2-maxpf >= 0) sol += cnt[maxpf];
        }
        for (auto x: v) {
            if (zag[x].val-zag[x].minpref <= 0) {
                ++cnt[-(zag[x].minpref)];
            }
        }
    }
    for (auto v: komp) {
        for (auto x: v) zag[x] = {0, 0, 0};
    }
    if (str[centroid-1] == '(') sol += cnt[1];

    for (auto x: sus[centroid]) {
        if (cent[x] == 0) centroidna(x);
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> str;
	for (int i=0; i<n-1; ++i) {
        int a, b; cin >> a >> b;
        sus[a].pb(b); sus[b].pb(a);
	}
	dfs(1); centroidna(1);
    cout << sol;

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60