QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320453#8212. Football in Osijekucup-team197#WA 2ms17300kbC++173.8kb2024-02-03 17:04:142024-02-03 17:04:15

Judging History

你现在查看的是最新测评结果

  • [2024-02-03 17:04:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:17300kb
  • [2024-02-03 17:04:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 5e5 + 7 ;

int n ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
int cycle_len[ MAXN ] ;
int cycle_id[ MAXN ] ; 

int used[ MAXN ] ;
int lvl[ MAXN ] ;
int dp[ MAXN ] ;
int ans[ MAXN ] ;
vector < int > adds ;

void mrk ( int x , int id ) {
    cycle_id[ x ] = id ;
    int spec = -1 ;
    for ( auto y : v[ x ] ) {
        if ( cycle_len[ y ] > 0 ) { continue ; }
        lvl[ y ] = lvl[ x ] + 1 ;
        mrk ( y , id ) ;
        if ( dp[ x ] < dp[ y ] + 1 ) {
            dp[ x ] = dp[ y ] + 1 ;
            spec = y ;
        }
    }
    for ( auto y : v[ x ] ) {
        if ( y != spec && dp[ y ] > 0 ) {
            adds.push_back ( dp[ y ] ) ;
        }
    }
}

int ctr[ MAXN ] ;

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        v[ a[ i ] ].push_back ( i ) ;
    }
    int mn_cycle = MAXN ;
    int mx_cycle = 0 ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( used[ i ] > 0 ) { continue ; }
        vector < int > aux ;
        int x = i ;
        while ( used[ x ] == false ) {
            used[ x ] = i ;
            aux.push_back ( x ) ;
            x = a[ x ] ;
        }
        if ( used[ x ] == i ) {
            int hh = 0 , sz = aux.size ( ) ;
            for ( int j = sz - 1 ; j >= 0 ; -- j ) {
                ++ hh ;
                if ( aux[ j ] == x ) { break ; }
            }
            ++ tp ;
            for ( int j = sz - 1 ; j >= sz - hh ; -- j ) {
                cycle_len[ aux[ j ] ] = hh ;
                cycle_id[ aux[ j ] ] = tp ;
            }
            mn_cycle = min ( mn_cycle , hh ) ;
            mx_cycle = max ( mx_cycle , hh ) ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cycle_len[ i ] > 0 ) {
            mrk ( i , cycle_id[ i ] ) ;
        }
    }
    map < int , pii > w ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cycle_len[ i ] > 0 ) {
            pii sr = { dp[ i ] , i } ;
            w[ cycle_id[ i ] ] = max ( w[ cycle_id[ i ] ] , sr ) ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( cycle_len[ i ] > 0 ) {
            if ( w[ cycle_id[ i ] ].se != i && dp[ i ] > 0 ) { adds.push_back ( dp[ i ] ) ; }
        }
    }
    pii spec = { 0 , 0 } ;
    for ( auto e : w ) {
        spec = max ( spec , make_pair ( e.se.fi + cycle_len[ e.se.se ] , e.fi ) ) ;
        ++ ctr[ cycle_len[ e.se.se ] ] ;
        -- ctr[ e.se.fi + cycle_len[ e.se.se ] + 1 ] ;
    }
    for ( auto e : w ) {
        if ( e.fi != spec.se ) { 
            adds.push_back ( e.se.fi + cycle_len[ e.se.se ] ) ;
        }
    }
    sort ( adds.begin ( ) , adds.end ( ) , greater < int > ( ) ) ;
    int sz = adds.size ( ) ;
    int sm = spec.fi ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        ans[ i ] = MAXN ; 
    }
    for ( int i = 0 ; i < sz ; ++ i ) {
        ans[ sm ] = i ;
        sm += adds[ i ] ;
    }
    ans[ sm ] = sz ;
    sm = 0 ;
    for ( int i = 1 ; i <= mx_cycle ; ++ i ) {
        sm += ctr[ i ] ;
        if ( sm > 0 ) { ans[ i ] = 0 ; }
        else { ans[ i ] = 1 ; }
    }
    for ( int i = n - 1 ; i >= mx_cycle + 1 ; -- i ) {
        ans[ i ] = min ( ans[ i ] , ans[ i + 1 ] ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cout << ans[ i ] << " " ;
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 16712kb

input:

5
2 3 1 3 5

output:

0 1 0 0 1 

result:

ok 5 number(s): "0 1 0 0 1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 15524kb

input:

1
1

output:

0 

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 16644kb

input:

2
2 2

output:

0 0 

result:

ok 2 number(s): "0 0"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 17300kb

input:

10
4 7 2 8 4 3 4 9 7 3

output:

1 1 1 0 0 0 0 1 2 500007 

result:

wrong answer 10th numbers differ - expected: '3', found: '500007'