Submission #1096586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096586		Doncho_Bonboncho	Game (APIO22_game)	C++17	0 / 100	10 ms	23896 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 > inline bool chkmin( T1& a, const T2& b ){ return a > b ? a = b, 1 : 0; };
template< class T1, class T2 > inline bool chkmax( T1& a, const T2& b ){ return a < b ? a = b, 1 : 0; };
const int MAX_N = 5e5 + 42;

#define out(x) #x << " = " << x << "   " 
#define endl "\n"


int L[MAX_N];
int R[MAX_N];

int K;
void init(int n, int k) {
	K = k;
	for( int i=0 ; i < n ; i++ ){
		if( i < k ){
			//L[i] = 0;
			//R[i] = k-1;
			L[i] = i;
			R[i] = i;
		}else{
			L[i] = k;
			R[i] = -1;
		}
	}

}

std::vector< int > e[MAX_N];
std::vector< int > rev[MAX_N];

bool nas = false;

bool viz[MAX_N];
int tt = 1;
void dfsL( int x ){
	viz[x] = tt;
	cerr << out( x ) << out( L[x] ) << out( R[x] ) << endl;
	for( auto j : e[x] ){
		cerr << out( j ) << endl;
		if( viz[j] >= tt ) continue;
		if( j < K ) continue;
		chkmin( L[j], L[x] );
		if( L[j] <= R[j] ) nas = true;
		dfsL( j );
	}
}

void dfsR( int x ){
	viz[x] = tt;
	cout << out( x ) << out( L[x] ) << out( R[x] ) << endl;
	for( auto j : rev[x] ){
		cerr << out( j ) << endl;
		if( viz[j] >= tt ) continue;
		if( j < K ) continue;
		if( R[x] < K ) chkmax( R[j], R[x] );
		if( L[j] <= R[j] ) nas = true;
		dfsR( j );
	}
}

int add_teleporter(int u, int v) {

	if( u < K and v < K ) return 1;

	cout << out( u ) << out( v ) << endl;
	e[v].push_back( u );
	rev[u].push_back( v );

	chkmin( L[u], L[v] );
	if( u < K ) chkmax( R[v], u );
	
	// nadolu
	tt ++;
	cerr << " dfsL " << endl;
	dfsL( u );

	// nagore
	tt ++;
	cerr << " dfsR " << endl;
	dfsR( v );

	return nas;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40