oj.uz

Submission #144940

# Submission time Handle Problem Language Result Execution time Memory
144940 2019-08-18T08:03:10 Z Abelyan Zagrade (COI17_zagrade) C++17
100 / 100
 1642 ms 50060 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=4e5+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

char c[N];
int qan=0;
vector<int> g[N],vc;
int sz[N];
ll ans;
bool col[N];

void dfssz(int v,int par=-1){
    sz[v]=1;
    qan++;
    trav(to,g[v]){
        if (col[to] || to==par) continue;
        dfssz(to,v);
        sz[v]+=sz[to];
    }
}

int get(int v,int par=-1){
    trav(to,g[v]){
        if (col[to] || to==par) continue;
        if (sz[to]>qan/2) return get(to,v);
    }
    return v;
}

set<pair<int,ll> > s;
set<pair<int,ll> >::iterator it;

void dfs1(int v,int pr,int mn,int par=-1){
    //if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
    if (c[v]=='('){
        pr++;
        mn++;
        mn=min(mn,1);
    }
    else{
        pr--;
        mn--;
        mn=min(mn,-1);
    }
    //if (v==3)cout<<v<<" "<<pr<<" "<<mn<<endl;
    if (mn>=0){
        it=s.lower_bound({pr,INT_MIN});
        if (it==s.end() || it->fr!=pr){
            s.insert({pr,1});
            //cout<<v<<" "<<pr<<endl;
        }
        else{
            pair<int,ll> tv=*it;
            tv.sc++;
            s.erase(it);
            s.insert(tv);
            //cout<<pr<<endl;
        }
    }
    trav(to,g[v])if (!col[to] && par!=to)dfs1(to,pr,mn,v);
}

void dfs2(int v,int pr,int mn,int par=-1){
    if (c[v]=='('){
        pr++;
    }
    else{
        pr--;
    }
    mn=min(mn,pr);
    if (mn==pr){
        vc.ad(pr);
        //cout<<"hey "<<pr<<endl;
    }
    trav(to,g[v])if (!col[to] && par!=to)dfs2(to,pr,mn,v);
}


void decomp(int v){
    qan=0;
    dfssz(v);
    int cent=get(v);
    //cout<<cent<<endl;
    FOR(i,g[cent].size()){
        int to=g[cent][i];
        if (col[to])continue;
        dfs2(to,0,0,cent);
        trav(tv,vc){
            it=s.lower_bound({-tv,INT_MIN});
            if (it->fr==-tv){
                ans+=it->sc;
            }
        }
        vc.clear();
        if (c[cent]=='(')
            dfs1(to,1,1,cent);
        else dfs1(to,-1,-1,cent);
    }
    while(!s.empty())s.erase(s.begin());
    if (c[cent]=='(')s.insert({1,1});
    FORD(i,g[cent].size()){
        int to=g[cent][i];
        if (col[to])continue;
        dfs2(to,0,0,cent);
        trav(tv,vc){
            //if (c[cent]=='C' && tv==-1)ans++;
            it=s.lower_bound({-tv,LLONG_MIN});
            if (it->fr==-tv){
                ans+=it->sc;
            }
        }
        vc.clear();
        if (c[cent]=='(')
            dfs1(to,1,1,cent);
        else dfs1(to,-1,-1,cent);
    }
    it=s.lower_bound({0,LLONG_MIN});
    //cout<<cent<<" "<<ans<<endl;
    if (it->fr==0){
        ans+=it->sc;
    }
    while(!s.empty())s.erase(s.begin());
    col[cent]=true;
    trav(to,g[cent]){
        if (!col[to])decomp(to);
    }
}

int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    //assert(n>=10);
    FORT(i,1,n){
        cin>>c[i];
    }
    FOR(i,n-1){
        int a,b;
        cin>>a>>b;
        g[a].ad(b);
        g[b].ad(a);
    }
    decomp(1);
    cout<<ans<<endl;
    return 0;
}

Compilation message

zagrade.cpp: In function 'void decomp(int)':
zagrade.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
zagrade.cpp:108:5: note: in expansion of macro 'FOR'
     FOR(i,g[cent].size()){
     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 14 ms 9848 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 12 ms 9848 KB Output is correct
10 Correct 11 ms 9980 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 39772 KB Output is correct
2 Correct 613 ms 40332 KB Output is correct
3 Correct 737 ms 39928 KB Output is correct
4 Correct 647 ms 40148 KB Output is correct
5 Correct 753 ms 39928 KB Output is correct
6 Correct 1076 ms 41208 KB Output is correct
7 Correct 740 ms 39832 KB Output is correct
8 Correct 1049 ms 41080 KB Output is correct
9 Correct 750 ms 39768 KB Output is correct
10 Correct 1622 ms 49908 KB Output is correct
11 Correct 820 ms 40184 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 14 ms 9848 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 12 ms 9848 KB Output is correct
10 Correct 11 ms 9980 KB Output is correct
11 Correct 741 ms 39772 KB Output is correct
12 Correct 613 ms 40332 KB Output is correct
13 Correct 737 ms 39928 KB Output is correct
14 Correct 647 ms 40148 KB Output is correct
15 Correct 753 ms 39928 KB Output is correct
16 Correct 1076 ms 41208 KB Output is correct
17 Correct 740 ms 39832 KB Output is correct
18 Correct 1049 ms 41080 KB Output is correct
19 Correct 750 ms 39768 KB Output is correct
20 Correct 1622 ms 49908 KB Output is correct
21 Correct 820 ms 40184 KB Output is correct
22 Correct 1316 ms 21524 KB Output is correct
23 Correct 1256 ms 21600 KB Output is correct
24 Correct 1322 ms 21624 KB Output is correct
25 Correct 1495 ms 21660 KB Output is correct
26 Correct 897 ms 27392 KB Output is correct
27 Correct 933 ms 24568 KB Output is correct
28 Correct 915 ms 23420 KB Output is correct
29 Correct 1642 ms 49952 KB Output is correct
30 Correct 1622 ms 50060 KB Output is correct
31 Correct 166 ms 22248 KB Output is correct
32 Correct 791 ms 40180 KB Output is correct