Submission #85842

#	Time	Username	Problem	Language	Result	Execution time	Memory
85842		nikolapesic2802	Zagrade (COI17_zagrade)	C++14	0 / 100	3036 ms	78856 KiB

zagrade

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a)-1)
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}
const int N=3e5+5;
const int M=INT_MIN/10;
const int L=INT_MIN/100;
struct segTree{
    vector<int> minn;
    vector<int> maxx;
    vector<int> lazy;
    vector<int> number;
    void init()
    {
        minn.resize(4*N);
        maxx.resize(4*N);
        number.resize(4*N);
        lazy.resize(4*N);
        fill(all(maxx),M);
        fill(all(minn),M);
    }
    void prop(int i)
    {
        lazy[2*i]+=lazy[i];
        lazy[2*i+1]+=lazy[i];
        minn[2*i]+=lazy[i];
        maxx[2*i]+=lazy[i];
        minn[2*i+1]+=lazy[i];
        maxx[2*i+1]+=lazy[i];
        lazy[i]=0;
    }
    void update(int i)
    {
        if(minn[2*i]<L)
            minn[i]=minn[2*i+1];
        else
        {
            if(minn[2*i+1]<L)
                minn[i]=minn[2*i];
            else
                minn[i]=min(minn[2*i],minn[2*i+1]);
        }
        if(maxx[2*i]<L)
            maxx[i]=maxx[2*i+1];
        else
        {
            if(maxx[2*i+1]<L)
                maxx[i]=maxx[2*i];
            else
                maxx[i]=max(maxx[2*i],maxx[2*i+1]);
        }
        number[i]=number[2*i]+number[2*i+1];
    }
    void fuck(int i=1,int l=0,int r=N-1)
    {
        if(minn[i]<L){
            number[i]=0;
            return;
        }
        if(minn[i]>1)
        {
            number[i]=0;
            return;
        }
        if(minn[i]==maxx[i])
        {
            if(minn[i]==1)
                number[i]=r-l+1;
            else
                number[i]=0;
            return;
        }
        int m=(l+r)>>1;
        prop(i);
        fuck(2*i,l,m);
        fuck(2*i+1,m+1,r);
        update(i);
    }
    void add(int qs,int qe,int x,int i=1,int l=0,int r=N-1)
    {
        //printf("%i %i %i\n",i,l,r);
        if(qs>r||qe<l)
            return;
        if(qs<=l&&qe>=r)
        {
            lazy[i]+=x;
            minn[i]+=x;
            maxx[i]+=x;
            if(minn[i]>L&&minn[i]<0)
                fuck();
            return;
        }
        //printf("d\n");
        prop(i);
        int m=(l+r)>>1;
        add(qs,qe,x,2*i,l,m);
        add(qs,qe,x,2*i+1,m+1,r);
        update(i);
    }
    void set(int poz,int i=1,int l=0,int r=N-1)
    {
        if(l>poz||r<poz)
            return;
        if(poz==l&&poz==r)
        {
            minn[i]=1;
            maxx[i]=1;
            number[i]=1;
            lazy[i]=0;
            return;
        }
        prop(i);
        int m=(l+r)>>1;
        set(poz,2*i,l,m);
        set(poz,2*i+1,m+1,r);
        update(i);
    }
} pocetak,kraj;
vector<int> finish;
vector<int> in(N),out(N);
vector<vector<int> > graf(N);
vector<int> sta(N);
int t=0;
void dfs(int tr,int par)
{
    in[tr]=t;
    for(auto p:graf[tr])
    {
        if(p==par)
            continue;
        t++;
        dfs(p,tr);
    }
    out[tr]=t;
    finish.pb(tr);
}
int main()
{
    pocetak.init();
    kraj.init();
    int n;
    scanf("%i",&n);
    string s;
    cin >> s;
    for(int i=0;i<n;i++)
    {
        sta[i]=s[i]==')';
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%i %i",&x,&y);
        x--;
        y--;
        graf[x].pb(y);
        graf[y].pb(x);
    }
    dfs(0,-1);
    ll cnt=0;
    for(auto p:finish)
    {
        //printf("Usao za %i  %i %i\n",p,in[p],out[p]);
        if(sta[p]==0)
        {
            //printf("Pocetak!\n");
            cnt+=kraj.number[1];
            pocetak.add(in[p],out[p],1);
            kraj.add(in[p],out[p],-1);
            pocetak.set(p);
        }
        else
        {
            //printf("Kraj!\n");
            cnt+=pocetak.number[1];
            //printf("1\n");
            pocetak.add(in[p],out[p],-1);
            //printf("1\n");
            kraj.add(in[p],out[p],1);
            //printf("1\n");
            kraj.set(p);
        }
    }
    printf("%lld\n",cnt/2);
    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
zagrade.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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