Submission #28835

#	Time	Username	Problem	Language	Result	Execution time	Memory
28835		samir_droubi	Zagrade (COI17_zagrade)	C++14	100 / 100	826 ms	49880 KiB

zagrade

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60