oj.uz

Submission #68544

# Submission time Handle Problem Language Result Execution time Memory
68544 2018-08-17T09:27:43 Z yusufake Shymbulak (IZhO14_shymbulak) C++
0 / 100
 110 ms 22448 KB 
#include <bits/stdc++.h>
using namespace std;

#define _ int v, int tl, int tr, int l, int r
#define tm (tl + tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r

typedef long long ll;
const int N = 4e5 + 3;

typedef long long ll;
typedef pair < ll , ll > pp;

#define pb push_back
#define mp make_pair
#define st first
#define nd second

vector < ll > V[N];

pp s[N*4],T[N],M[N];
ll ans[N],W[N],H[N],t,n,i,j,x,y;

pp mrg(pp a, pp b){
    if(a<b) swap(a,b);
    return mp(a.st,a.nd+(a.st==b.st)*b.nd);
}
pp qry(_){
    if(tl > r || tr < l) return mp(-N,0);
    if(tl >= l && tr <= r) return s[v];
    return mrg( qry(sol) , qry(sag) );
}
pp bld(_){
    if(tl == tr) return s[v] = mp(T[tl].st-tl,T[tl].nd);
    return s[v] = mrg( bld(sol) , bld(sag) );
}

pp g(int x, int p){
    pp a=mp(0,1);
    for(auto y : V[x]){
        if(!H[y] || y == p) continue;
        pp t = g(y,x);
        t.st++;
        ans[ a.st+t.st ] += a.nd*t.nd;
        if(a.st < t.st) a=t;
        else if(a.st == t.st) a.nd += t.nd;
    }
    return M[x] = a;
}

void f(int x){
    H[x] = 1;
    T[++t] = M[x];
    //cout << t << " " << x << " "<< T[t].st << " " << T[t].nd << " zz\n";
    for(int i=0; i<V[x].size(); i++)
        if(!H[ V[x][i] ])
            f(V[x][i]);
}

int main(){
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);
        V[x].pb(y); V[y].pb(x); W[x]++; W[y]++;
    }

    for(i=1;i<=n;i++){
        for(x = i; W[x] == 1; x = y){
            W[x]--;
            y = 0;
            H[x] = 1;
            for(j=0;j<V[x].size();j++){
                W[ V[x][j] ]--;
                if(W[ V[x][j] ] == 1){
                    y = x;
                }
            }
        }
    }

    for(i=1;i<=n;i++) if(!H[i]) g(i,-1);
    for(i=1;i<=n;i++) if(!H[i]) f(i);

    //cout << t << " zz\n"; 
    for(i=1;i<=t;i++) T[t+i] = T[i];
    bld(1,1,t+t,0,0);
    for(i=t/2+1;i<=t+t/2;i++){
        if(t == 1) break;
            pp a = qry(1,1,t+t,i-t/2,i-1);
            ans[ a.st + T[i].st+i ] += T[i].nd*a.nd;
    }

    for(i=n; i ;i--)
        if(ans[i]){
            //cout << i << " aa  ";
            printf("%lld",ans[i]);
            return 0;
        }
    assert(0);
}

Compilation message

shymbulak.cpp: In function 'pp qry(int, int, int, int, int)':
shymbulak.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
shymbulak.cpp:6:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
shymbulak.cpp:32:21: note: in expansion of macro 'sol'
     return mrg( qry(sol) , qry(sag) );
                     ^~~
shymbulak.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
shymbulak.cpp:7:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
shymbulak.cpp:32:32: note: in expansion of macro 'sag'
     return mrg( qry(sol) , qry(sag) );
                                ^~~
shymbulak.cpp: In function 'pp bld(int, int, int, int, int)':
shymbulak.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
shymbulak.cpp:6:20: note: in expansion of macro 'tm'
 #define sol v+v,tl,tm,l,r
                    ^~
shymbulak.cpp:36:28: note: in expansion of macro 'sol'
     return s[v] = mrg( bld(sol) , bld(sag) );
                            ^~~
shymbulak.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
shymbulak.cpp:7:19: note: in expansion of macro 'tm'
 #define sag v+v+1,tm+1,tr,l,r
                   ^~
shymbulak.cpp:36:39: note: in expansion of macro 'sag'
     return s[v] = mrg( bld(sol) , bld(sag) );
                                       ^~~
shymbulak.cpp: In function 'void f(int)':
shymbulak.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<V[x].size(); i++)
                  ~^~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<V[x].size();j++){
                     ~^~~~~~~~~~~~
shymbulak.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
shymbulak.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9828 KB Output is correct
3 Correct 9 ms 9828 KB Output is correct
4 Correct 10 ms 9940 KB Output is correct
5 Incorrect 9 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10160 KB Output is correct
2 Correct 9 ms 10212 KB Output is correct
3 Incorrect 10 ms 10212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 22448 KB Output isn't correct
2 Halted 0 ms 0 KB -