oj.uz

Submission #480687

# Submission time Handle Problem Language Result Execution time Memory
480687 2021-10-17T18:16:56 Z MOUF_MAHMALAT Zagrade (COI17_zagrade) C++14
100 / 100
 1091 ms 54088 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,c[300009],x,y,ans,sz[300009];
bool is[300009];
char cc;
vector<vector<ll> >v;
map<ll,ll>mp;
void dfs(ll d,ll p)
{
    sz[d]=1;
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        dfs(z,d);
        sz[d]+=sz[z];
    }
}
ll centroid(ll d,ll p,ll op)
{
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        if(sz[z]>op)
            return centroid(z,d,op);
    }
    return d;
}
void best(ll d,ll p,ll cur,ll mx,bool b)
{
    cur+=c[d];
    mx=max(mx,cur);
    if(cur>=mx)
        mp[cur]++;
    if(cur<0)
        b=0;
    if(cur>=mx&&cur==0)
        ans++;
    if(b&&cur==0)
        ans++;
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        best(z,d,cur,mx,b);
    }
}
void rem(ll d,ll p,ll cur,ll mx)
{
    cur+=c[d];
    mx=max(mx,cur);
    if(cur>=mx)
        mp[cur]--;
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        rem(z,d,cur,mx);
    }
}
void add(ll d,ll p,ll cur,ll mx)
{
    cur+=c[d];
    mx=max(mx,cur);
    if(cur>=mx)
        mp[cur]++;
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        add(z,d,cur,mx);
    }
}
void op(ll d,ll p,ll cur,ll mn)
{
    cur+=c[d];
    mn=min(mn,cur);
    if(cur<=mn)
        ans+=mp[-cur];
    for(auto z:v[d])
    {
        if(z==p||is[z])
            continue;
        op(z,d,cur,mn);
    }
}
void calc(ll o)
{
    dfs(o,o);
    o=centroid(o,o,sz[o]/2);
    is[o]=1;
    mp.clear();
    best(o,o,0,0,1);
    if(c[o]==1)
        mp[1]--;
    for(auto z:v[o])
    {
        if(is[z])
            continue;
        rem(z,z,c[o],max(0LL,c[o]));
        op(z,o,0,0);
        add(z,z,c[o],max(0LL,c[o]));
    }
    for(auto z:v[o])
        if(!is[z])
            calc(z);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    v.resize(n+1);
    for(ll i=1; i<=n; i++)
    {
        cin>>cc;
        if(cc=='(')
            c[i]=1;
        else
            c[i]=-1;
    }
    for(ll i=1; i<n; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    /*for(ll i=1;i<n;i++)
        v[i].push_back(i+1),v[i+1].push_back(i);*/
    calc(1);
    cout<<ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 41020 KB Output is correct
2 Correct 664 ms 48484 KB Output is correct
3 Correct 522 ms 44740 KB Output is correct
4 Correct 647 ms 47484 KB Output is correct
5 Correct 554 ms 44744 KB Output is correct
6 Correct 688 ms 46008 KB Output is correct
7 Correct 512 ms 44740 KB Output is correct
8 Correct 723 ms 45968 KB Output is correct
9 Correct 523 ms 44728 KB Output is correct
10 Correct 1091 ms 54088 KB Output is correct
11 Correct 479 ms 44828 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 538 ms 41020 KB Output is correct
12 Correct 664 ms 48484 KB Output is correct
13 Correct 522 ms 44740 KB Output is correct
14 Correct 647 ms 47484 KB Output is correct
15 Correct 554 ms 44744 KB Output is correct
16 Correct 688 ms 46008 KB Output is correct
17 Correct 512 ms 44740 KB Output is correct
18 Correct 723 ms 45968 KB Output is correct
19 Correct 523 ms 44728 KB Output is correct
20 Correct 1091 ms 54088 KB Output is correct
21 Correct 479 ms 44828 KB Output is correct
22 Correct 1004 ms 27560 KB Output is correct
23 Correct 1000 ms 27572 KB Output is correct
24 Correct 953 ms 27576 KB Output is correct
25 Correct 1006 ms 27580 KB Output is correct
26 Correct 646 ms 33480 KB Output is correct
27 Correct 694 ms 30848 KB Output is correct
28 Correct 651 ms 29712 KB Output is correct
29 Correct 1051 ms 54068 KB Output is correct
30 Correct 1004 ms 54028 KB Output is correct
31 Correct 104 ms 27316 KB Output is correct
32 Correct 455 ms 44616 KB Output is correct