Submission #86854

#	Time	Username	Problem	Language	Result	Execution time	Memory
86854		nikolapesic2802	Zagrade (COI17_zagrade)	C++14	0 / 100	463 ms	66244 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;
vector<vector<int> > graf(N),drvo(N);
vector<int> visited(N),siz(N),local(N),what(N);
void dfs(int tr,int par)
{
    local[tr]=0;
    siz[tr]=1;
    for(auto p:graf[tr])
    {
        if(visited[p]||p==par)
            continue;
        dfs(p,tr);
        siz[tr]+=siz[p];
    }
}
int find_centroid(int tr,int n)
{
    local[tr]=1;
    for(auto p:graf[tr])
    {
        if(local[p]||visited[p])
            continue;
        if(siz[p]>n/2)
            return find_centroid(p,n);
    }
    return tr;
}
int decompose(int tr)
{
    dfs(tr,-1);
    tr=find_centroid(tr,siz[tr]);
    visited[tr]=1;
    for(auto p:graf[tr])
    {
        if(visited[p])
            continue;
        int t=decompose(p);
        //printf("%i--%i\n",tr,t);
        drvo[t].pb(tr);
        drvo[tr].pb(t);
    }
    return tr;
}
ll cnt=0;
vector<int> allowed(N),str,fin,start(N),finish(N);
void calculate(int tr,int par,int offset)
{
    //printf("Calculatujem %i\n",tr);
    if(what[tr]==0){
        offset++;
        if(offset>=0)
        {
            str.pb(offset);
            //printf("Dodajem start %i\n",offset);
        }
    }
    else{
        offset--;
        if(offset<=0)
        {
            fin.pb(-1*offset);
            //printf("Dodajem finish %i\n",offset*-1);
        }
    }
    for(auto p:graf[tr])
    {
        if(allowed[p]==0||p==par)
            continue;
        calculate(p,tr,offset);
    }
}
void solve(int tr,int par)
{
    for(auto p:drvo[tr])
    {
        if(p==par)
            continue;
        solve(p,tr);
    }
    int off;
    if(what[tr]==0)
        off=1;
    else
        off=-1;
    //printf("Solvujem %i %lld\n",tr,cnt);
    vector<int> s,f;
    for(auto p:graf[tr])
    {
        if(allowed[p]){
            calculate(p,tr,0);
            for(auto p:str)
            {
                if(off+p>=0)
                    cnt+=finish[p+off];
                s.pb(p);
            }
            for(auto p:fin){
                if(p-off>=0)
                    cnt+=start[p-off];
                finish[p]++;
                f.pb(p);
            }
            for(auto p:str)
                start[p]++;
            str.clear();
            fin.clear();
        }
    }
    //printf("%i %i %i\n",tr,what[tr],finish[1]);
    allowed[tr]=1;
    if(what[tr]==0)
        cnt+=finish[1];
    else
        cnt+=start[1];
    for(auto p:s)
        start[p]=0;
    for(auto p:f)
        finish[p]=0;
}
int main()
{
	int n;
	scanf("%i",&n);
	string s;
	cin >> s;
	for(int i=0;i<n;i++)
        what[i+1]=s[i]==')';
	for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%i %i",&a,&b);
        graf[a].pb(b);
        graf[b].pb(a);
    }
    int root=decompose(1);
    //printf("Root: %i\n",root);
    solve(root,-1);
    printf("%lld\n",cnt);
    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:153:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
zagrade.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

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