oj.uz

Submission #387832

# Submission time Handle Problem Language Result Execution time Memory
387832 2021-04-09T09:08:34 Z RohamIzadidoost Fun Tour (APIO20_fun) C++14
21 / 100
 638 ms 126380 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
pii p ;
int cur , mark[maxn] , n , H[4 * maxn] , val[4 * maxn] , X , pt; 
set<pii> seg[4 * maxn] ; 
void build(int x = 0 , int lx = 0 , int rx = pt , int h = 1 ){
	H[x] = h ; 
	seg[x].insert({-h , x}) ;
	//cout<<x <<" : " << H[x] <<" boom " << endl ; 
	int mid = lx + rx >> 1 ; 
	if(2 * x + 1 < n){
		build( 2 * x + 1 , lx , mid , h + 1) ;
		for(auto u : seg[x * 2 + 1]) seg[x].insert(u) ; 
	}
	if(2 * x + 2 < n){
		build(2 * x + 2 , mid , rx , h + 1) ;
		for(auto u : seg[x * 2 + 2]) seg[x].insert(u) ;
	}
//	cout<<x <<" : " ; for(auto u : seg[x]) cout<<u.X <<"," << u.Y <<"  " ; cout<<endl ; 
//	sort(all(seg[x])) ; 
}
void del(int x){
	seg[x].erase({-H[X] , X}) ;
	if(x == 0) return ;
	x = (x - 1) / 2 ; 
	del(x) ;
}
pii dfs(int v){
	int x  , V = v ;; 
	p = {0 , 0} ;
	if(v == 0 ){
		p = {seg[0].begin() -> X - 1 , seg[0].begin() -> Y} ;
		return p ; 
	}
	while(v != 0){
	//	cout<<"DFS : " << v <<" , " << V << endl ;  
		x = v ; 
		v = (v - 1) / 2 ;
		if(x & 1) x = 2 * v + 2 ; 
		else x = 2 * v + 1 ; 
		if(SZ(seg[x])) p = max(p ,{ H[V] + (-1 * (seg[x].begin() -> X) ) - 2 * H[v] , seg[x].begin() -> Y } ) ;  
	}
	return p ; 
}
	vec<int> ans ;
vec<int> createFunTour(int N , int Q){
	n = N ; 
	pt = 1 ; 
	while(pt < n ) pt *= 2 ; 
	build() ; 
	ans.pb(seg[1].begin() -> Y) ;
	while(SZ(ans) < n){
		//cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl   ; 
		X = ans.back() ; 
		del(ans.back()) ; 
		ans.pb(dfs(ans.back()).Y) ; 
	}
//	for(int i = 0 ;  i < n ; i ++ ) ans[i] = val[ans[i]] ;
	return ans ; 
}

/*int main()
{
	migmig ;
	cin>>n ; 
	pt = 1 ; 
	while(pt < n ) pt *= 2 ; 
	build() ; 
	ans.pb(seg[1].begin() -> Y) ;
	while(SZ(ans) < n){
	//	cout<<SZ(ans) <<" : " << ans.back() << " -> " << val[ans.back()] << endl   ; 
		X = ans.back() ; 
		del(ans.back()) ; 
		ans.pb(dfs(ans.back()).Y) ; 
	}
//	for(int i = 0 ;  i < n ; i ++ ) ans[i] = val[ans[i]] ;
	for(auto u : ans) cout<<u <<" " ; 
}*/

Compilation message

fun.cpp: In function 'void build(int, int, int, int)':
fun.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 37928 KB Tour is not fun

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 37928 KB Tour is not fun

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37876 KB Output is correct
2 Correct 23 ms 37836 KB Output is correct
3 Correct 23 ms 37856 KB Output is correct
4 Correct 24 ms 37792 KB Output is correct
5 Correct 24 ms 37892 KB Output is correct
6 Correct 23 ms 37900 KB Output is correct
7 Correct 23 ms 37868 KB Output is correct
8 Correct 23 ms 37780 KB Output is correct
9 Correct 25 ms 37876 KB Output is correct
10 Correct 23 ms 37824 KB Output is correct
11 Correct 23 ms 37876 KB Output is correct
12 Correct 25 ms 38092 KB Output is correct
13 Correct 23 ms 37836 KB Output is correct
14 Correct 23 ms 37828 KB Output is correct
15 Correct 23 ms 37936 KB Output is correct
16 Correct 24 ms 38040 KB Output is correct
17 Correct 25 ms 38092 KB Output is correct
18 Correct 638 ms 126380 KB Output is correct
19 Correct 25 ms 38348 KB Output is correct
20 Correct 30 ms 38988 KB Output is correct
21 Correct 32 ms 39788 KB Output is correct
22 Correct 47 ms 42576 KB Output is correct
23 Correct 80 ms 47812 KB Output is correct
24 Correct 104 ms 51492 KB Output is correct
25 Correct 357 ms 87460 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37876 KB Output is correct
2 Correct 23 ms 37836 KB Output is correct
3 Correct 23 ms 37836 KB Output is correct
4 Incorrect 23 ms 37844 KB Tour is not fun
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 37928 KB Tour is not fun