Submission #1156871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156871		kitkat12	Zagrade (COI17_zagrade)	C++20	10 / 100	329 ms	43880 KiB

zagrade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 3e5+10;
int l[nmax],sz[nmax],r[nmax];
vector<int> adj[nmax];

int dfs_sz(int u, int par=-1){
    sz[u]=1;
    for(int v:adj[u]){
        if(v==par || r[v])continue;
        sz[u]+=dfs_sz(v,u);
    }
    return sz[u];
}

int get_cent(int u, int ts, int par=-1){
    for(int v : adj[u]){
        if(par==v || r[v])continue;
        if(sz[v]*2>ts)return get_cent(v,ts,u);
    }
    return u;
}

int rcnt[2*nmax],lcnt[2*nmax];
int res=0;

void slv_cent(int u, int par, bool fill, int v, int minv, int maxv, int root){
    v+=l[u];
    minv=min(minv,v);
    maxv=max(maxv,v);

    // valid left
    if(v >= maxv){
        if(fill){
            res+=rcnt[-(v+l[root])+nmax];
        }   
        else{
            lcnt[v+nmax]++;
        }
    }

    // valid right
    if(v <= minv){
        if(fill){
            res+=lcnt[-(v+l[root])+nmax];
        }
        else{
            rcnt[v+nmax]++;
        }
    }

    for(int to : adj[u]){
        if(to==par||r[to])continue;
        slv_cent(to,u,fill,v,minv,maxv,root);
    }
}

void del(int u, int par, int v){
    v+=l[u];
    lcnt[v+nmax]=rcnt[v+nmax]=0;
    for(int to : adj[u]){
        if(to==par||r[to])continue;
        del(to,u,v);
    }
}

void solve(int u){
    u = get_cent(u,dfs_sz(u));
    r[u]=1;

    lcnt[nmax]++;
    rcnt[nmax]++;
    for(int v : adj[u]){
        if(r[v])continue;
        slv_cent(v,u,true,0,0,0,u);
        slv_cent(v,u,false,0,0,0,u);
    }

    // clear l/r cnt
    lcnt[nmax]=rcnt[nmax]=0;
    for(int v:adj[u]){
        if(r[v])continue;
        del(v,u,0);
    }

    for(int v:adj[u]){
        if(r[v])continue;
        solve(v);
    }
}

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    char in;
    int n;
    cin>>n;
    li(i,1,n+1){
        cin>>in;
        l[i]=(in=='('?1:-1);
    }
    int a,b;
    li(i,0,n-1){
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    mem(r,0);
    mem(rcnt,0);
    mem(lcnt,0);
    solve(1);

    cout<<res;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60