oj.uz

Submission #86293

# Submission time Handle Problem Language Result Execution time Memory
86293 2018-11-26T01:08:32 Z nikolapesic2802 Zagrade (COI17_zagrade) C++14
100 / 100
 864 ms 187412 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;
pair<int,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 mp(pocetak.size()-1,kraj.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++)
    {
        pair<int,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.second].count(1);
            pocetak[tren.first].delta++;
            kraj[tren.second].delta--;
            kraj[tren.second].erase();
        }
        else
        {
            cnt+=pocetak[tren.first].count(1);
            pocetak[tren.first].delta--;
            kraj[tren.second].delta++;
            pocetak[tren.first].erase();
        }
        vector<int> al=pocetak[tren.first].all_elements();
        for(auto p:al)
        {
            //printf("%i: Dodao: %i\n",tr,p);
            dodao.pb(p);
            poc.insert(p);
        }
        al=kraj[tren.second].all_elements();
        for(auto p:al)
        {
            //printf("%i: Dodaokraj: %i\n",tr,p);
            dodaok.pb(p);
            krj.insert(p);
        }
    }
    pair<int,int> tren=solve(ind[ind.size()-1].second,tr);
    if(sta[tr]==0)
    {
        cnt+=kraj[tren.second].count(1);
        pocetak[tren.first].delta++;
        kraj[tren.second].delta--;
        kraj[tren.second].erase();
        pocetak[tren.first].insert(1);
    }
    else
    {
        cnt+=pocetak[tren.first].count(1);
        pocetak[tren.first].delta--;
        kraj[tren.second].delta++;
        pocetak[tren.first].erase();
        kraj[tren.second].insert(1);
    }
    for(auto p:dodao)
    {
        //printf("%i: brisem %i\n",tr,p);
        poc.erase(p);
        pocetak[tren.first].insert(p);
    }
    for(auto p:dodaok)
    {
        //printf("%i: brisem kraj %i\n",tr,p);
        krj.erase(p);
        kraj[tren.second].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:249:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
zagrade.cpp:259: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 12 ms 7544 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 9 ms 7760 KB Output is correct
4 Correct 10 ms 7760 KB Output is correct
5 Correct 11 ms 7796 KB Output is correct
6 Correct 10 ms 7796 KB Output is correct
7 Correct 9 ms 7868 KB Output is correct
8 Correct 10 ms 7872 KB Output is correct
9 Correct 10 ms 7872 KB Output is correct
10 Correct 9 ms 7904 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 161644 KB Output is correct
2 Correct 442 ms 161744 KB Output is correct
3 Correct 363 ms 161812 KB Output is correct
4 Correct 435 ms 161812 KB Output is correct
5 Correct 338 ms 161812 KB Output is correct
6 Correct 399 ms 161812 KB Output is correct
7 Correct 360 ms 161812 KB Output is correct
8 Correct 416 ms 161812 KB Output is correct
9 Correct 369 ms 161812 KB Output is correct
10 Correct 431 ms 164200 KB Output is correct
11 Correct 307 ms 164200 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7544 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 9 ms 7760 KB Output is correct
4 Correct 10 ms 7760 KB Output is correct
5 Correct 11 ms 7796 KB Output is correct
6 Correct 10 ms 7796 KB Output is correct
7 Correct 9 ms 7868 KB Output is correct
8 Correct 10 ms 7872 KB Output is correct
9 Correct 10 ms 7872 KB Output is correct
10 Correct 9 ms 7904 KB Output is correct
11 Correct 346 ms 161644 KB Output is correct
12 Correct 442 ms 161744 KB Output is correct
13 Correct 363 ms 161812 KB Output is correct
14 Correct 435 ms 161812 KB Output is correct
15 Correct 338 ms 161812 KB Output is correct
16 Correct 399 ms 161812 KB Output is correct
17 Correct 360 ms 161812 KB Output is correct
18 Correct 416 ms 161812 KB Output is correct
19 Correct 369 ms 161812 KB Output is correct
20 Correct 431 ms 164200 KB Output is correct
21 Correct 307 ms 164200 KB Output is correct
22 Correct 809 ms 164200 KB Output is correct
23 Correct 818 ms 164200 KB Output is correct
24 Correct 853 ms 164200 KB Output is correct
25 Correct 864 ms 164200 KB Output is correct
26 Correct 515 ms 164200 KB Output is correct
27 Correct 535 ms 164200 KB Output is correct
28 Correct 555 ms 164200 KB Output is correct
29 Correct 405 ms 178360 KB Output is correct
30 Correct 397 ms 182668 KB Output is correct
31 Correct 336 ms 182668 KB Output is correct
32 Correct 316 ms 187412 KB Output is correct