#include "Joi.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long
using namespace std ;
vector<int> ordem ;
vector< vector<int> > adj ;
vector<bool> vis ;
void dfs(int x)
{
vis[x] = true ;
ordem.push_back(x) ;
for(auto e : adj[x])
{
if(vis[e]) continue ;
dfs(e) ;
ordem.push_back(x) ;
}
}
int isOn(int i, ll x ) { return ((1LL<<i)&x) != 0; }
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
adj.resize( N+10 , vector<int>() ) ;
vis.resize(N+10,false) ;
for(int i= 0 ; i < M ; i++ )
{
adj[ A[i] ].push_back( B[i] ) ;
adj[ B[i] ].push_back( A[i] ) ;
}
for(int i = 0 ; i < N ; i++ ) sort(all(adj[i]));
dfs(0) ;
vector<int> freq(60, 0) ;
vector<int> val(N+10, -1) ;
set<int> holdingOn ;
for(int i = 0 ; i < sz(ordem) ; i++ )
{
if( i-121 >= 0 && val[ordem[i-121]]!= -1 && (--freq[ val[ordem[i-121]] ]) == 0 && sz(holdingOn) > 0)
{
int x = *holdingOn.begin() ;
holdingOn.erase( holdingOn.begin() ) ;
val[x] = val[ordem[i-121]] ;
for(int j = i-120 ; j <= i ; j++ )
if( ordem[j] == x ) freq[ val[x] ]++ ;
}
if(val[ ordem[i] ] == -1)
{
for(int j = 0 ; j < 60 ; j++ )
if(freq[j] == 0)
{
val[ ordem[i] ] = j ;
break ;
}
if( val[ordem[i]] == -1 ) holdingOn.insert(ordem[i]) ;
else if( holdingOn.find(ordem[i]) != holdingOn.end() )
holdingOn.erase( holdingOn.find(ordem[i]) ) ;
}
if( val[ordem[i]] != -1 )
freq[ val[ ordem[i] ] ]++ ;
}
for(int i = 0 ; i < N ; i++ )
MessageBoard( i, isOn(val[i] , X) ) ;
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define debug printf
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long
using namespace std ;
vector<int> ord , tin , tout ;
vector< vector<int> > graph ;
vector<bool> mark ;
void dfsPrime(int x)
{
tin[x] = tout[x] = sz(ord);
mark[x] = true ;
ord.push_back(x) ;
for(auto e : graph[x])
{
if(mark[e]) continue ;
dfsPrime(e) ;
tout[x] = sz(ord) ;
ord.push_back(x) ;
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
graph.resize( N+10 , vector<int>() );
tin.resize(N+10);
tout.resize(N+10) ;
mark.resize(N+10,false) ;
for(int i= 0 ; i < M ; i++ )
{
graph[ A[i] ].push_back( B[i] ) ;
graph[ B[i] ].push_back( A[i] ) ;
}
for(int i = 0 ; i < N ; i++ ) sort(all(graph[i]));
dfsPrime(0) ;
vector<int> freq(60, 0) ;
vector<int> val(N+10, -1) ;
set<int> holdingOn ;
for(int i = 0 ; i < sz(ord) ; i++ )
{
if( i-121 >= 0 && val[ord[i-121]]!= -1 && (--freq[ val[ord[i-121]] ]) == 0 && sz(holdingOn) > 0)
{
int x = *holdingOn.begin() ;
holdingOn.erase( holdingOn.begin() ) ;
val[x] = val[ord[i-121]] ;
for(int j = i-120 ; j <= i ; j++ )
if( ord[j] == x ) freq[ val[x] ]++ ;
}
if(val[ ord[i] ] == -1)
{
for(int j = 0 ; j < 60 ; j++ )
if(freq[j] == 0)
{
val[ ord[i] ] = j ;
break ;
}
if( val[ord[i]] == -1 ) holdingOn.insert(ord[i]) ;
else if( holdingOn.find(ord[i]) != holdingOn.end() )
holdingOn.erase( holdingOn.find(ord[i]) ) ;
}
if( val[ord[i]] != -1 )
freq[ val[ ord[i] ] ]++ ;
}
int ptrBeg , ptrEn ;
for(int i = 0 ; i < sz(ord) ; i++ )
if(ord[i] == P) { ptrBeg = ptrEn = i ; break ; }
vector<int> achei(60,0) ;
achei[ val[P] ] = V ;
int qtd = 20000 ;
while(qtd--)
{
//cout << ptrBeg << " " << ptrEn << " " << qtd << " " << tin[P]<<" " << tout[P] << " " << P << endl ;
if( ptrBeg == tin[P] && ptrEn == tout[P] )
{
if(ptrBeg == 0 || ptrEn+1 == sz(ord)) break ;
P = ord[ptrBeg-1] ;
achei[ val[P] ] = Move(P) ;
ptrBeg-- ;
ptrEn++ ;
}
else
{
if( ptrBeg > tin[P] )
{
achei[ val[ ord[ptrBeg-1] ] ] = Move(ord[ptrBeg-1]) ;
ptrBeg-- ;
}
else
{
achei[ val[ord[ptrEn+1]] ] = Move(ord[ptrEn+1]);
ptrEn++ ;
}
}
}
ll x = 0LL ;
for(int i = 0 ; i< 60 ; i++ )
x += (1LL<<i) * achei[i] ;
return x ;
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:108:26: warning: 'ptrEn' may be used uninitialized in this function [-Wmaybe-uninitialized]
108 | if(ptrBeg == 0 || ptrEn+1 == sz(ord)) break ;
| ~~~~~^~
Ioi.cpp:122:51: warning: 'ptrBeg' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | achei[ val[ ord[ptrBeg-1] ] ] = Move(ord[ptrBeg-1]) ;
| ~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1012 KB |
Output is correct |
2 |
Correct |
2 ms |
980 KB |
Output is correct |
3 |
Correct |
2 ms |
988 KB |
Output is correct |
4 |
Correct |
2 ms |
772 KB |
Output is correct |
5 |
Correct |
2 ms |
1016 KB |
Output is correct |
6 |
Correct |
2 ms |
772 KB |
Output is correct |
7 |
Correct |
2 ms |
1164 KB |
Output is correct |
8 |
Correct |
2 ms |
988 KB |
Output is correct |
9 |
Correct |
2 ms |
908 KB |
Output is correct |
10 |
Correct |
2 ms |
900 KB |
Output is correct |
11 |
Correct |
5 ms |
1080 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
2 ms |
908 KB |
Output is correct |
14 |
Correct |
2 ms |
988 KB |
Output is correct |
15 |
Correct |
2 ms |
780 KB |
Output is correct |
16 |
Correct |
2 ms |
984 KB |
Output is correct |
17 |
Correct |
2 ms |
908 KB |
Output is correct |
18 |
Correct |
2 ms |
992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
4636 KB |
Output is correct |
2 |
Correct |
40 ms |
4884 KB |
Output is correct |
3 |
Correct |
41 ms |
4616 KB |
Output is correct |
4 |
Correct |
30 ms |
3788 KB |
Output is correct |
5 |
Correct |
28 ms |
3656 KB |
Output is correct |
6 |
Correct |
30 ms |
3660 KB |
Output is correct |
7 |
Correct |
28 ms |
3932 KB |
Output is correct |
8 |
Correct |
30 ms |
4056 KB |
Output is correct |
9 |
Correct |
28 ms |
3916 KB |
Output is correct |
10 |
Correct |
27 ms |
3344 KB |
Output is correct |
11 |
Correct |
27 ms |
3336 KB |
Output is correct |
12 |
Correct |
27 ms |
3260 KB |
Output is correct |
13 |
Correct |
28 ms |
3388 KB |
Output is correct |
14 |
Correct |
27 ms |
3268 KB |
Output is correct |
15 |
Correct |
30 ms |
3604 KB |
Output is correct |
16 |
Correct |
32 ms |
3464 KB |
Output is correct |
17 |
Correct |
28 ms |
3644 KB |
Output is correct |
18 |
Correct |
28 ms |
3404 KB |
Output is correct |
19 |
Correct |
30 ms |
3448 KB |
Output is correct |
20 |
Correct |
24 ms |
3664 KB |
Output is correct |
21 |
Correct |
23 ms |
3564 KB |
Output is correct |
22 |
Correct |
28 ms |
3528 KB |
Output is correct |
23 |
Correct |
28 ms |
3944 KB |
Output is correct |
24 |
Correct |
31 ms |
4032 KB |
Output is correct |
25 |
Correct |
30 ms |
4016 KB |
Output is correct |
26 |
Correct |
28 ms |
3864 KB |
Output is correct |
27 |
Correct |
28 ms |
3940 KB |
Output is correct |
28 |
Correct |
30 ms |
4084 KB |
Output is correct |
29 |
Correct |
27 ms |
3588 KB |
Output is correct |
30 |
Correct |
27 ms |
3904 KB |
Output is correct |
31 |
Correct |
2 ms |
1008 KB |
Output is correct |
32 |
Correct |
2 ms |
992 KB |
Output is correct |
33 |
Correct |
2 ms |
992 KB |
Output is correct |
34 |
Correct |
2 ms |
772 KB |
Output is correct |
35 |
Correct |
2 ms |
876 KB |
Output is correct |
36 |
Correct |
1 ms |
772 KB |
Output is correct |
37 |
Correct |
0 ms |
1012 KB |
Output is correct |
38 |
Correct |
1 ms |
1028 KB |
Output is correct |
39 |
Correct |
1 ms |
1028 KB |
Output is correct |
40 |
Correct |
2 ms |
1008 KB |
Output is correct |
41 |
Correct |
2 ms |
772 KB |
Output is correct |
42 |
Correct |
1 ms |
900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1020 KB |
Output is correct |
2 |
Correct |
1 ms |
900 KB |
Output is correct |
3 |
Correct |
2 ms |
880 KB |
Output is correct |
4 |
Incorrect |
4 ms |
1444 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
40 ms |
4644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
43 ms |
4648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |