oj.uz

답안 #144938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144938 2019-08-18T07:58:54 Z Abelyan Zagrade (COI17_zagrade) C++17
10 / 100
 1480 ms 47628 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;
    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:107:5: note: in expansion of macro 'FOR'
     FOR(i,g[cent].size()){
     ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 12 ms 9720 KB Output is correct
4 Correct 12 ms 9720 KB Output is correct
5 Correct 11 ms 9724 KB Output is correct
6 Correct 12 ms 9848 KB Output is correct
7 Correct 12 ms 9828 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 12 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 715 ms 39784 KB Output is correct
2 Correct 599 ms 40236 KB Output is correct
3 Correct 736 ms 39896 KB Output is correct
4 Correct 626 ms 40180 KB Output is correct
5 Correct 738 ms 39732 KB Output is correct
6 Correct 993 ms 40956 KB Output is correct
7 Correct 746 ms 39848 KB Output is correct
8 Correct 1000 ms 40836 KB Output is correct
9 Correct 717 ms 39676 KB Output is correct
10 Correct 1480 ms 47628 KB Output is correct
11 Incorrect 779 ms 40180 KB Output isn't correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 12 ms 9720 KB Output is correct
3 Correct 12 ms 9720 KB Output is correct
4 Correct 12 ms 9720 KB Output is correct
5 Correct 11 ms 9724 KB Output is correct
6 Correct 12 ms 9848 KB Output is correct
7 Correct 12 ms 9828 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 12 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 715 ms 39784 KB Output is correct
12 Correct 599 ms 40236 KB Output is correct
13 Correct 736 ms 39896 KB Output is correct
14 Correct 626 ms 40180 KB Output is correct
15 Correct 738 ms 39732 KB Output is correct
16 Correct 993 ms 40956 KB Output is correct
17 Correct 746 ms 39848 KB Output is correct
18 Correct 1000 ms 40836 KB Output is correct
19 Correct 717 ms 39676 KB Output is correct
20 Correct 1480 ms 47628 KB Output is correct
21 Incorrect 779 ms 40180 KB Output isn't correct