| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144979 |
2019-08-18T10:13:06 Z |
emilem |
Zagrade (COI17_zagrade) |
C++14 |
|
857 ms |
20668 KB |
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long ans;
int n;
int op, clos;
string path;
vector< vector<int> > nei;
string a;
long long Chain(const string& a)
{
vector< pair<int, int> > pref(a.length());
for (int i = 0; i < pref.size(); ++i)
{
pref[i].second = i;
if (a[i] == '(') ++pref[i].first;
else --pref[i].first;
if (i) pref[i].first += pref[i - 1].first;
}
vector<int> r(n, -1);
for (int i = 0; i < n; ++i)
{
r[i] = -1;
int minElem = pref[i].first;
for (int j = i; j < n; ++j)
{
minElem = min(minElem, pref[j].first);
if (minElem - (i ? pref[i - 1].first : 0) < 0)
break;
else
r[i] = j;
}
}
sort(pref.begin(), pref.end());
for (int i = 0; i < n; ++i)
if (r[i] != -1)
for (int j = i; j < n && pref[j].second <= r[i]; ++j)
if (pref[j].first == (i ? pref[i - 1].first : 0))
++ans;
else
break;
return 0;
}
void Dfs(int v, int par)
{
if (op == clos && a[v] == ')')
return;
if (a[v] == ')') ++clos;
else ++op;
path += a[v];
if (clos == op)
++ans;
for (int i = 0; i < nei[v].size(); ++i)
{
int to = nei[v][i];
if (to == par) continue;
Dfs(to, v);
}
path.pop_back();
if (a[v] == ')') --clos;
else --op;
}
int main()
{
cin >> n;
nei.resize(n);
cin >> a;
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v; --u; --v;
nei[u].push_back(v);
nei[v].push_back(u);
}
if (false/*n <= 1000*/)
{
for (int v = 0; v < n; ++v)
{
op = clos = 0;
path = "";
Dfs(v, -1);
}
cout << ans << endl;
return 0;
}
else // Is a chain.
{
ans += Chain(a);
reverse(a.begin(), a.end());
ans += Chain(a);
cout << ans << endl;
char I;
cin >> I;
}
char I;
cin >> I;
}
Compilation message
zagrade.cpp: In function 'long long int Chain(const string&)':
zagrade.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pref.size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:40:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (r[i] != -1)
^
zagrade.cpp: In function 'void Dfs(int, int)':
zagrade.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nei[v].size(); ++i)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
857 ms |
20668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
