Submission #229799

#	Time	Username	Problem	Language	Result	Execution time	Memory
229799		CaroLinda	Islands (IOI08_islands)	C++14	90 / 100	808 ms	131076 KiB

islands

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAXN = 1e6+10 ;

using namespace std ;

int N ;
int to[MAXN] ;
ll resp , best_diameter ;
ll W[MAXN] , D[MAXN] ;
ll prof[MAXN][2] ;
vector< int > adj[MAXN] ;
bool vis[MAXN] ;

void dfs( int x )
{
    vis[x] = true ;

    for(int child : adj[x] )
    {
        if(vis[child]) continue ;

        dfs(child) ;

        if( prof[child][0] + W[child] >= prof[x][0] )
        {
            prof[x][1] = prof[x][0] ;
            prof[x][0] = prof[child][0] + W[child] ;
        }
        else if( prof[child][0] + W[child] > prof[x][1] )
            prof[x][1] = prof[child][0] + W[child] ;

    }

    best_diameter = max( best_diameter, prof[x][0] + prof[x][1] ) ;

}

inline void new_cycle(int x)
{
    vector<int> cycle ;
    while( !vis[x] )
    {
        vis[x] = true ;
        cycle.pb(x) ;
        x = to[x] ;
    }

    reverse( all(cycle) ) ;

    for(int i = cycle.size() - 1 ; cycle[i] != x ; i -- )
    {
        vis[ cycle[i] ] = false ;
        cycle.pop_back() ;
    }

    reverse( all(cycle) ) ;


    best_diameter = 0 ;

    ll sum = 0LL , t = 0LL ;

    for(int i = 0 ; i < cycle.size() ; i++ )
    {
        dfs( cycle[i] ) ;
        sum += W[ cycle[i] ] ;
        if( i ) D[ cycle[i] ] = D[ cycle[i-1] ] + W[ cycle[i-1] ] ;
    }

    for(int i = 0 ; i < cycle.size() ; i++ )
    {
        if( i ) best_diameter = max( best_diameter , t + D[ cycle[i] ] + prof[ cycle[i] ][0] ) ;
        t = max(t , -D[ cycle[i] ] + prof[ cycle[i] ][0] ) ;
    }

    t = 0LL ;
    for(int i = 0 ; i < cycle.size() ; i++ )
    {
        if(i) best_diameter = max( best_diameter , sum - D[ cycle[i] ] + prof[ cycle[i] ][0] + t ) ;
        t = max( t , D[ cycle[i] ] + prof[ cycle[i] ][0] ) ;
    }

    resp += best_diameter ;

}

int main()
{
    scanf("%d", &N ) ;
    for(int i = 1 , u ; i <= N ; i++ )
    {
        scanf("%d%d", &to[i] , &W[i] ) ;
        adj[ to[i] ].pb(i) ;
    }

    for(int i = 1 ; i <= N ; i++ )
        if( !vis[i] ) new_cycle(i) ;

    printf("%lld\n" , resp ) ;

}

Compilation message (stderr)

islands.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
islands.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
islands.cpp: In function 'void new_cycle(int)':
islands.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < cycle.size() ; i++ )
                     ~~^~~~~~~~~~~~~~
islands.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < cycle.size() ; i++ )
                     ~~^~~~~~~~~~~~~~
islands.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < cycle.size() ; i++ )
                     ~~^~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:108:38: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
         scanf("%d%d", &to[i] , &W[i] ) ;
                                ~~~~~ ^
islands.cpp:106:21: warning: unused variable 'u' [-Wunused-variable]
     for(int i = 1 , u ; i <= N ; i++ )
                     ^
islands.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N ) ;
     ~~~~~^~~~~~~~~~~
islands.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &to[i] , &W[i] ) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10