# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244142 | MatesV13 | Zagrade (COI17_zagrade) | C++11 | 2921 ms | 1048580 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b, ans;
char z[300005];
vector<int> c[300005];
multiset<int> zag[2][300005];
void help(int idx){
cout << "Obraduje se " << idx << endl;
cout << "0: (";
for (multiset<int>::iterator it=zag[0][idx].begin(); it!=zag[0][idx].end(); it++)
cout << *it << " ";
cout << ")" << endl;
cout << "1: (";
for (multiset<int>::iterator it=zag[1][idx].begin(); it!=zag[1][idx].end(); it++)
cout << *it << " ";
cout << ")" << endl;
cout << "Trenutni ans je " << ans << endl << endl;
}
void solve(int idx, int par){
for (int i=0; i<c[idx].size(); i++)
if (c[idx][i]!=par)
solve(c[idx][i], idx);
int vrsta;
if (z[idx]=='(') vrsta=1;
else vrsta=-1;
/* for (int i=0; i<c[idx].size(); i++){
for (multiset<int>::iterator it=zag[0][c[idx][i]].begin(); it!=zag[0][c[idx][i]].end(); it++)
for (int j=i+1; j<c[idx].size(); j++){
ans+=(1LL*zag[1][c[idx][j]].count(*it+vrsta));
}
for (multiset<int>::iterator it=zag[1][c[idx][i]].begin(); it!=zag[1][c[idx][i]].end(); it++)
for (int j=i+1; j<c[idx].size(); j++){
ans+=(1LL*zag[0][c[idx][j]].count(*it+vrsta));
}
} */
for (int i=0; i<c[idx].size(); i++){
for (multiset<int>::iterator it=zag[1][c[idx][i]].begin(); it!=zag[1][c[idx][i]].end(); it++){
if ((*it)+vrsta>=0) zag[1][idx].insert((*it)+vrsta);
}
}
for (int i=0; i<c[idx].size(); i++){
for (multiset<int>::iterator it=zag[0][c[idx][i]].begin(); it!=zag[0][c[idx][i]].end(); it++){
if ((*it)+vrsta<=0) zag[0][idx].insert((*it)+vrsta);
}
}
ans+=zag[1][idx].count(0)+ zag[0][idx].count(0);
for (multiset<int>::iterator it=zag[0][idx].begin(); it!=zag[0][idx].end(); it++)
if (*it!=vrsta and *it!=0) ans += zag[1][idx].count(-(*it-vrsta));
if (vrsta==1) zag[1][idx].insert(1);
else zag[0][idx].insert(-1);
// help(idx);
return;
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++) cin >> z[i];
for (int i=1; i<n; i++){
cin >> a >> b;
c[a].push_back(b);
c[b].push_back(a);
} solve(1, 0);
cout << ans;
return 0;
}
/*
6
((()))
1 2
2 3
3 4
4 5
5 6
3
(()
1 3
2 3
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |