oj.uz

Submission #144936

# Submission time Handle Problem Language Result Execution time Memory
144936 2019-08-18T07:56:09 Z Abelyan Zagrade (COI17_zagrade) C++17
10 / 100
 1446 ms 47720 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],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<pir> s;
set<pir>::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{
            pir 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,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);
    }
    it=s.lower_bound({0,INT_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;
    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:107: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 9852 KB Output is correct
2 Correct 11 ms 9724 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 12 ms 9868 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9848 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 12 ms 9720 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 39792 KB Output is correct
2 Correct 589 ms 40184 KB Output is correct
3 Correct 732 ms 39872 KB Output is correct
4 Correct 610 ms 40216 KB Output is correct
5 Correct 725 ms 39800 KB Output is correct
6 Correct 991 ms 40736 KB Output is correct
7 Correct 734 ms 39800 KB Output is correct
8 Correct 993 ms 40824 KB Output is correct
9 Correct 726 ms 39772 KB Output is correct
10 Correct 1446 ms 47720 KB Output is correct
11 Incorrect 800 ms 40280 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9852 KB Output is correct
2 Correct 11 ms 9724 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 12 ms 9868 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9848 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 12 ms 9720 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 716 ms 39792 KB Output is correct
12 Correct 589 ms 40184 KB Output is correct
13 Correct 732 ms 39872 KB Output is correct
14 Correct 610 ms 40216 KB Output is correct
15 Correct 725 ms 39800 KB Output is correct
16 Correct 991 ms 40736 KB Output is correct
17 Correct 734 ms 39800 KB Output is correct
18 Correct 993 ms 40824 KB Output is correct
19 Correct 726 ms 39772 KB Output is correct
20 Correct 1446 ms 47720 KB Output is correct
21 Incorrect 800 ms 40280 KB Output isn't correct