oj.uz

Submission #229806

# Submission time Handle Problem Language Result Execution time Memory
229806 2020-05-06T15:47:04 Z CaroLinda Islands (IOI08_islands) C++14
100 / 100
 878 ms 131072 KB 
#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];
vector<int> cycle ;
vector< int > adj[MAXN] ;
bool vis[MAXN] ;

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

    ll p2 = 0LL ;

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

        dfs(child) ;

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

    }

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

}

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 j=1 ; j <= N ; j++ )
    {
        if(vis[j]) continue ;

        cycle.clear() ;
        int x = j ;

        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] ] ) ;
            t = max(t , -D[ cycle[i] ] + prof[ cycle[i] ] ) ;
        }

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

        resp += best_diameter ;
    }

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

}

Compilation message

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 'int main()':
islands.cpp:62: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:60:21: warning: unused variable 'u' [-Wunused-variable]
     for(int i = 1 , u ; i <= N ; i++ )
                     ^
islands.cpp:95:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < cycle.size() ; i++ )
                         ~~^~~~~~~~~~~~~~
islands.cpp:102:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < cycle.size() ; i++ )
                         ~~^~~~~~~~~~~~~~
islands.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < cycle.size() ; i++ )
                         ~~^~~~~~~~~~~~~~
islands.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N ) ;
     ~~~~~^~~~~~~~~~~
islands.cpp:62: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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 20 ms 23808 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 24064 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24576 KB Output is correct
2 Correct 32 ms 25472 KB Output is correct
3 Correct 28 ms 24832 KB Output is correct
4 Correct 25 ms 24448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 26240 KB Output is correct
2 Correct 56 ms 28792 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 33144 KB Output is correct
2 Correct 94 ms 35824 KB Output is correct
3 Correct 119 ms 36336 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 43256 KB Output is correct
2 Correct 198 ms 46828 KB Output is correct
3 Correct 209 ms 55660 KB Output is correct
4 Correct 280 ms 55656 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 40540 KB Output is correct
2 Correct 612 ms 62664 KB Output is correct
3 Correct 328 ms 61000 KB Output is correct
4 Correct 396 ms 71404 KB Output is correct
5 Correct 383 ms 69352 KB Output is correct
6 Correct 852 ms 65044 KB Output is correct
7 Correct 420 ms 73188 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 131072 KB Output is correct
2 Correct 450 ms 114836 KB Output is correct
3 Correct 435 ms 95336 KB Output is correct
4 Correct 414 ms 86844 KB Output is correct
5 Correct 387 ms 83176 KB Output is correct
6 Correct 396 ms 83188 KB Output is correct
7 Correct 878 ms 83444 KB Output is correct