Submission #119690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
119690	2019-06-21T20:36:08 Z	OptxPrime	Deblo (COCI18_deblo)	C++11	90 / 90	694 ms	24696 KB

deblo

#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>

using namespace std;

#define pb push_back
#define mp make_pair

    /// COCI DEBLO 2018 CONTEST 2
    /// SKONTO: ZA SVAKI OD 30AK BITOVA, GRADIMO DP NA STABLO.
    /// DP[X][Y] SU PUTEVI KOJIMA JE X POCETNI CVOR I IDU PREMA DOLE, ILI JE X PRELOMNICA, TJ.
    /// IDE IZ NEKOG DJETETA U DRUGO. Y PREDSTAVLJA SAMO PARNOST.
    /// KOMBINUJEMO SAD NE PRETESKO: AKO X IMA FIKSAN TAJ BIT, ONDA UZMEMO ZBIR PARNE DJECE, I JOS
    /// PROIZVOD ZBIRA NEPARNE I NEPARNE, KAO I PARNE I PARNE DJECE, JER SU TO SVI MOGUCI
    /// PUTEVI KOJI CE ZADOVOLJAVATI.
    /// PROBAT OVO IMPLEMENTIRATI

    ///GRESKA U LOGICI: KAD DODAJEM PUTEVE U NEKI CVOR, DODAM I NEVALIDNE, JER DODAM ONE STO SE GRANAJU NA GORNJI..

    /// preispito sam opet, fakat se cini dobro
    /// 10 22

    /// OPET NEKI PROBLEMI

    int n;
    long long val[100010];
    long long dp[100010][2];
    long long res[100010];
    long long tot[100010][2];
    int par[100010];
    vector<vector<int>> adjl;

    long long dfs( int x, int p, bool paran, long long bit )
    {
        // cout << x<< " " <<paran<<" "<<bit<<endl;
        if( dp[x][paran]!=-1 ) return dp[x][paran];
        /// mozda je problem u ovom -1, mada sumnjam
        par[x]=p;
        bool type;
        if( val[x]&bit  ) type=1;
        else type=0;
        if( adjl[x].size()<=1 ){
            if( x==0 ) 1;
            else if( type==paran && x!=0 ) return tot[x][paran]=dp[x][paran]=1;
           else return tot[x][paran]=dp[x][paran]=0;
        }
        long long sumap=0,suman=0,sqrp=0,sqrn=0,mix=0;
        for( int i=0;i<adjl[x].size();i++ ){
            int v=adjl[x][i];
            if( v==par[x] ) continue;
            long long tmp1=dfs(v,x,0,bit);
            sumap+=tmp1;
            sqrp+=tmp1*tmp1;
            long long tmp2=dfs(v,x,1,bit);
            suman+=tmp2;
            sqrn+=tmp2*tmp2;
            mix+=tmp1*tmp2;
        }
    //    cout << " eto " <<endl;
        /// sad tek ide apdejt;

        if( type!= paran ){
     //   if( bit==1 && x==1 ) cout <<suman << " " << mix << " konju " <<endl;
             dp[x][paran]=tot[x][paran]=0;
            dp[x][paran]+=suman;       /// putevi koji pocinjju u x i silaze
        tot[x][paran] = dp[x][paran];
        tot[x][paran]+=(suman*sumap);
        tot[x][paran]-=mix;
    //    cout <<x << " " << bit << " " << tot[x][paran ]  << " karagaa " <<endl;
        }
        else{
         //   cout <<x <<" " << bit << " "<< type << " " << paran << " "<<  sumap << " " << suman << " " << sqrp << " eee " <<sqrn<<endl;
        //  if( bit == 4 && x == 2  ) cout << sumap << " " << suman << " lokum " << sqrp <<endl;
            dp[x][paran]=tot[x][paran]=1;
            dp[x][paran]+=sumap;
            tot[x][paran]=dp[x][paran];
            long long tmp = ( sumap*sumap - sqrp )/2;
        tot[x][paran]+=tmp;
            tmp=( suman*suman - sqrn )/2;

        tot[x][paran]+=tmp;
        }
    //    if( tot[x][paran] ==-1 ) cout << " koji breee " <<endl;
        return dp[x][paran];
    }

int main()
{
    int u,v;
    cin>>n;
    adjl.resize(n);

    for( int i=0;i<n;i++ ){
        cin>>val[i];
        dp[i][0]=dp[i][1]=-1;
    }
    for( int i=0;i<n-1;i++ ){
        cin>>u>>v;
        u--;
        v--;
        adjl[u].pb( v );
        adjl[v].pb( u );
    }
  //  cout << adjl[3].size() << " debilu " <<endl;
    long long res=0;
    par[0]=-1;
    for( int j=0;j<22;j++ ){
            for( int i=0;i<n;i++ ) dp[i][0]=dp[i][1]= tot[i][0]=tot[i][1]=-1;
        for(int i=0;i<n;i++){
            //cout << j << " " << i << " eto " <<endl;
            //dp[i][0]=dp[i][1]=-1;

           // long long curr=dfs( i, par[i],1,( 1<<j ) );
           if( tot[i][1]!=-1 ) res+=tot[i][1]*( 1<<j );
           else {
                dfs( i,par[i],1,( 1<<j ) );
                /// ovdje ispod bude tot[i] -1 bez razloga, a gore u dfs nikad ne bude. kako ti
          //      cout << i << " " << (1<<j) << "  " << tot[i][1] << " totittt " <<endl;
                res+=tot[i][1]*( 1<<j );
           }
          //  res+=dfs( i,par[i],1, (1<<j) )*( (1<<j) );
          //  cout<<( 1<<j ) << " " << i << " "<< dp[i][0] << " " << dp[i][1] << " glavno " <<curr  <<endl;
            //if( j==0 ) cout << dp[4][1] << " kiko " <<endl;
        }
   //     for( int i=0;i<n;i++ ) cout<<(1<<j) << " " << i << " " << tot[i][0] << " " << tot[i][1] << " " <<dp[i][1] << " bhal "<<endl;
    }



    cout<<res<<endl;

    return 0;
}

Compilation message

deblo.cpp: In function 'long long int dfs(int, int, bool, long long int)':
deblo.cpp:47:25: warning: statement has no effect [-Wunused-value]
             if( x==0 ) 1;
                         ^
deblo.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<adjl[x].size();i++ ){
                      ~^~~~~~~~~~~~~~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	269 ms	24696 KB	Output is correct
7	Correct	272 ms	24440 KB	Output is correct
8	Correct	249 ms	14584 KB	Output is correct
9	Correct	264 ms	13240 KB	Output is correct
10	Correct	694 ms	12024 KB	Output is correct