oj.uz

Submission #86432

# Submission time Handle Problem Language Result Execution time Memory
86432 2018-11-26T09:54:42 Z nikolapesic2802 Zagrade (COI17_zagrade) C++14
100 / 100
 943 ms 163096 KB 
#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 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;
ll cnt=0;
int sta[N];
int sz[N];
vector<vector<int> > graf(N);
void dfs(int tr,int par)
{
    sz[tr]=1;
    for(auto p:graf[tr])
    {
        if(p==par)
            continue;
        dfs(p,tr);
        sz[tr]+=sz[p];
    }
}
struct str{
    set<pair<int,int> > set1;
    int delta;
    void insert(int i,int p=1)
    {
        i-=delta;
        if(set1.lower_bound({i,0})==set1.end())
        {
            set1.insert({i,p});
            return;
        }
        pair<int,int> a=*set1.lower_bound({i,0});
        if(a.first==i)
        {
            set1.erase(a);
            a.second+=p;
            set1.insert(a);
        }
        else
        {
            set1.insert({i,p});
        }
    }
    int count(int i)
    {
        i-=delta;
        if(set1.lower_bound({i,0})==set1.end())
            return 0;
        pair<int,int> a=*set1.lower_bound({i,0});
        if(a.first==i)
            return a.second;
        return 0;
    }
    int size()
    {
        return set1.size();
    }
    void erase(int i)
    {
        i-=delta;
        pair<int,int> a=*set1.lower_bound({i,0});
        if(a.first==i)
        {
            set1.erase(a);
            a.second--;
            if(a.second>0)
                set1.insert(a);
        }
        else
        {
            assert(0);
        }
    }
    int erase()
    {
        int obr=0;
        while(set1.size()&&(*set1.begin()).first+delta<0){
            assert((*set1.begin()).first+delta==-1);
            obr=((*set1.begin()).second);
            set1.erase(set1.begin());
        }
        return obr;
    }
    vector<int> all_elements()
    {
        vector<int> al;
        for(auto p:set1)
        {
            for(int i=0;i<p.second;i++)
                al.pb(p.first+delta);
        }
        return al;
    }
} e;
vector<str> pocetak,kraj;
str poc,krj;
int solve(int tr,int par)
{
    //printf("%i %i\n",tr,par);

    //printf("%i: %lld\n",tr,cnt);
    if(graf[tr].size()==1&&tr!=0)
    {
        //printf("Usao!\n");
        if(sta[tr]==0)
            cnt+=krj.count(1);
        else
            cnt+=poc.count(1);
        pocetak.pb(e);
        kraj.pb(e);
        if(sta[tr]==0)
            pocetak.back().insert(1);
        else
            kraj.back().insert(1);
        return pocetak.size()-1;
    }
    int obr;
    if(sta[tr]==0)
    {
        cnt+=krj.count(1);
        poc.delta++;
        krj.delta--;
        obr=krj.erase();
    }
    else
    {
        cnt+=poc.count(1);
        poc.delta--;
        krj.delta++;
        obr=poc.erase();
    }
    //printf("Prosao!\n");
    vector<pair<int,int> > ind;
    for(auto p:graf[tr])
    {
        if(p==par)
            continue;
        ind.pb({sz[p],p});
    }
    sort(ind.begin(),ind.end());
    vector<int> dodao,dodaok;
    for(int i=0;i<(int)ind.size()-1;i++)
    {
        int tren=solve(ind[i].second,tr);
        //printf("%i: %i %i %i\n",tr,tren.first,tren.second,ind.size());
        if(sta[tr]==0)
        {
            cnt+=kraj[tren].count(1);
            pocetak[tren].delta++;
            kraj[tren].delta--;
            kraj[tren].erase();
        }
        else
        {
            cnt+=pocetak[tren].count(1);
            pocetak[tren].delta--;
            kraj[tren].delta++;
            pocetak[tren].erase();
        }
        vector<int> al=pocetak[tren].all_elements();
        for(auto p:al)
        {
            //printf("%i: Dodao: %i\n",tr,p);
            dodao.pb(p);
            poc.insert(p);
        }
        al=kraj[tren].all_elements();
        for(auto p:al)
        {
            //printf("%i: Dodaokraj: %i\n",tr,p);
            dodaok.pb(p);
            krj.insert(p);
        }
    }
    int tren=solve(ind[ind.size()-1].second,tr);
    if(sta[tr]==0)
    {
        cnt+=kraj[tren].count(1);
        pocetak[tren].delta++;
        kraj[tren].delta--;
        kraj[tren].erase();
        pocetak[tren].insert(1);
    }
    else
    {
        cnt+=pocetak[tren].count(1);
        pocetak[tren].delta--;
        kraj[tren].delta++;
        pocetak[tren].erase();
        kraj[tren].insert(1);
    }
    for(auto p:dodao)
    {
        poc.erase(p);
        pocetak[tren].insert(p);
    }
    for(auto p:dodaok)
    {
        krj.erase(p);
        kraj[tren].insert(p);
    }
    if(sta[tr]==0)
    {
        if(obr)
            krj.insert(-1,obr);
        poc.delta--;
        krj.delta++;
    }
    else
    {
        if(obr)
            poc.insert(-1,obr);
        poc.delta++;
        krj.delta--;
    }
    return tren;
}
int main()
{
    e.set1.clear();
    e.delta=0;
    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);
    solve(0,-1);
    printf("%lld\n",cnt);
    return 0;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:247:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
zagrade.cpp:257: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7548 KB Output is correct
2 Correct 10 ms 7624 KB Output is correct
3 Correct 10 ms 7624 KB Output is correct
4 Correct 10 ms 7692 KB Output is correct
5 Correct 9 ms 7780 KB Output is correct
6 Correct 10 ms 7780 KB Output is correct
7 Correct 13 ms 7992 KB Output is correct
8 Correct 10 ms 7992 KB Output is correct
9 Correct 10 ms 7992 KB Output is correct
10 Correct 12 ms 7992 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 160500 KB Output is correct
2 Correct 500 ms 160712 KB Output is correct
3 Correct 409 ms 160712 KB Output is correct
4 Correct 460 ms 160712 KB Output is correct
5 Correct 353 ms 160712 KB Output is correct
6 Correct 417 ms 160712 KB Output is correct
7 Correct 347 ms 160712 KB Output is correct
8 Correct 414 ms 160712 KB Output is correct
9 Correct 391 ms 160712 KB Output is correct
10 Correct 411 ms 162876 KB Output is correct
11 Correct 301 ms 162876 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7548 KB Output is correct
2 Correct 10 ms 7624 KB Output is correct
3 Correct 10 ms 7624 KB Output is correct
4 Correct 10 ms 7692 KB Output is correct
5 Correct 9 ms 7780 KB Output is correct
6 Correct 10 ms 7780 KB Output is correct
7 Correct 13 ms 7992 KB Output is correct
8 Correct 10 ms 7992 KB Output is correct
9 Correct 10 ms 7992 KB Output is correct
10 Correct 12 ms 7992 KB Output is correct
11 Correct 360 ms 160500 KB Output is correct
12 Correct 500 ms 160712 KB Output is correct
13 Correct 409 ms 160712 KB Output is correct
14 Correct 460 ms 160712 KB Output is correct
15 Correct 353 ms 160712 KB Output is correct
16 Correct 417 ms 160712 KB Output is correct
17 Correct 347 ms 160712 KB Output is correct
18 Correct 414 ms 160712 KB Output is correct
19 Correct 391 ms 160712 KB Output is correct
20 Correct 411 ms 162876 KB Output is correct
21 Correct 301 ms 162876 KB Output is correct
22 Correct 861 ms 162876 KB Output is correct
23 Correct 943 ms 162876 KB Output is correct
24 Correct 911 ms 162876 KB Output is correct
25 Correct 902 ms 162876 KB Output is correct
26 Correct 505 ms 162876 KB Output is correct
27 Correct 521 ms 162876 KB Output is correct
28 Correct 535 ms 162876 KB Output is correct
29 Correct 390 ms 162952 KB Output is correct
30 Correct 386 ms 163096 KB Output is correct
31 Correct 321 ms 163096 KB Output is correct
32 Correct 305 ms 163096 KB Output is correct