QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#320453 | #8212. Football in Osijek | ucup-team197# | WA | 2ms | 17300kb | C++17 | 3.8kb | 2024-02-03 17:04:14 | 2024-02-03 17:04:15 |
Judging History
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'