oj.uz

Submission #28835

# Submission time Handle Problem Language Result Execution time Memory
28835 2017-07-17T09:35:06 Z samir_droubi Zagrade (COI17_zagrade) C++14
100 / 100
 826 ms 49880 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int mxn=(3e5)+5;
int a[mxn];
vector<int>tr[mxn];
bool used[mxn];
int sz[mxn];
void dfs(int v,int p)
{
    sz[v]=1;
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p||used[u])continue;
        dfs(u,v);
        sz[v]+=sz[u];
    }
}
int S;
int mn;
int nd;
void dfs1(int v,int p)
{
    int mx=S-sz[v];
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p||used[u])continue;
        mx=max(mx,sz[u]);
        dfs1(u,v);
    }
    if(mx<mn)
    {
        mn=mx;
        nd=v;
    }
}
int cnt[mxn];
int cnt1[mxn];
vector<int>vv;
vector<int>vv1;
ll ans=0;
void dfs2(int v,int p,int mnp,int mns,int s)
{
    int nmnp=min(mnp,s+a[nd]);
    int nmns=min(a[nd],mns+a[nd]);
    int ns=s+a[nd];
    
    if(mnp>=0)
    {
        vv.push_back(s);
        ans=(ans+cnt1[s]);
    }
    if(nmns>=ns&&ns<=0)
    {
        vv1.push_back(abs(ns));
        ans=(ans+cnt[abs(ns)]);
    }
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p||used[u])continue;
        dfs2(u,v,min(a[u],mnp+a[u]),min(mns,s+a[u]),s+a[u]);
    }
}
void divide(int x)
{
    dfs(x,x);
    S=sz[x];
    mn=(1e9);
    nd=-1;
    dfs1(x,x);
    if(nd==-1)return;
    int md=nd;
    used[md]=true;

    vv.clear();
    vv1.clear();
    int ls=0;
    int ls1=0;
    if(a[nd]<0)++cnt1[1];
    for(int i=0;i<tr[nd].size();++i)
    {
        int u=tr[nd][i];
        if(used[u])continue;
        dfs2(u,u,a[u],a[u],a[u]);
        for(int j=ls;j<vv.size();++j)++cnt[vv[j]];
        for(int j=ls1;j<vv1.size();++j)++cnt1[vv1[j]];
        ls=vv.size();
        ls1=vv1.size();
    }
    if(a[nd]<0)--cnt1[1];

    while(!vv.empty())
    {
        --cnt[vv.back()];
        vv.pop_back();
    }

    while(!vv1.empty())
    {
        --cnt1[vv1.back()];
        vv1.pop_back();
    }

    for(int i=0;i<tr[md].size();++i)
    {
        int u=tr[md][i];
        if(used[u])continue;
        divide(u);
    }
}
int main()
{
    cnt[0]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        char c;
        cin>>c;
        if(c=='(')a[i]=1;
        else a[i]=-1;
    }
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    divide(1);
    printf("%lld\n",ans);
    return 0;
}

Compilation message

zagrade.cpp: In function 'void dfs(int, int)':
zagrade.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
zagrade.cpp: In function 'void dfs1(int, int)':
zagrade.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
zagrade.cpp: In function 'void dfs2(int, int, int, int, int)':
zagrade.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
zagrade.cpp:47:9: warning: unused variable 'nmnp' [-Wunused-variable]
     int nmnp=min(mnp,s+a[nd]);
         ^
zagrade.cpp: In function 'void divide(int)':
zagrade.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[nd].size();++i)
                  ^
zagrade.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=ls;j<vv.size();++j)++cnt[vv[j]];
                       ^
zagrade.cpp:90:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=ls1;j<vv1.size();++j)++cnt1[vv1[j]];
                        ^
zagrade.cpp:108:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[md].size();++i)
                  ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:118:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
zagrade.cpp:129:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 46724 KB Output is correct
2 Correct 489 ms 48348 KB Output is correct
3 Correct 383 ms 46716 KB Output is correct
4 Correct 456 ms 48340 KB Output is correct
5 Correct 416 ms 46724 KB Output is correct
6 Correct 449 ms 47572 KB Output is correct
7 Correct 419 ms 46720 KB Output is correct
8 Correct 429 ms 47580 KB Output is correct
9 Correct 446 ms 46720 KB Output is correct
10 Correct 423 ms 49880 KB Output is correct
11 Correct 466 ms 49376 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14036 KB Output is correct
2 Correct 3 ms 14036 KB Output is correct
3 Correct 0 ms 14036 KB Output is correct
4 Correct 3 ms 14036 KB Output is correct
5 Correct 0 ms 14036 KB Output is correct
6 Correct 3 ms 14036 KB Output is correct
7 Correct 6 ms 14036 KB Output is correct
8 Correct 0 ms 14036 KB Output is correct
9 Correct 3 ms 14036 KB Output is correct
10 Correct 3 ms 14036 KB Output is correct
11 Correct 433 ms 46724 KB Output is correct
12 Correct 489 ms 48348 KB Output is correct
13 Correct 383 ms 46716 KB Output is correct
14 Correct 456 ms 48340 KB Output is correct
15 Correct 416 ms 46724 KB Output is correct
16 Correct 449 ms 47572 KB Output is correct
17 Correct 419 ms 46720 KB Output is correct
18 Correct 429 ms 47580 KB Output is correct
19 Correct 446 ms 46720 KB Output is correct
20 Correct 423 ms 49880 KB Output is correct
21 Correct 466 ms 49376 KB Output is correct
22 Correct 826 ms 24844 KB Output is correct
23 Correct 763 ms 24980 KB Output is correct
24 Correct 756 ms 24852 KB Output is correct
25 Correct 726 ms 24856 KB Output is correct
26 Correct 493 ms 31236 KB Output is correct
27 Correct 583 ms 27808 KB Output is correct
28 Correct 476 ms 26484 KB Output is correct
29 Correct 353 ms 49880 KB Output is correct
30 Correct 369 ms 49880 KB Output is correct
31 Correct 163 ms 28624 KB Output is correct
32 Correct 443 ms 49376 KB Output is correct