Submission #1096592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096592		Doncho_Bonboncho	Game (APIO22_game)	C++17	0 / 100	9 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;

#ifndef LOCAL
#define cerr if(false)cerr
#endif

#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;

int 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 : rev[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 : e[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 from, int to) {

	if( from < K and to < K ) return 1;

	cout << out( from ) << out( to ) << endl;
	e[from].push_back( to );
	rev[to].push_back( from );

	chkmin( L[from], L[to] );
	chkmax( R[to], R[from] );
	
	// nadolu
	tt ++;
	cerr << " dfsL " << endl;
	dfsL( from );

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

	return nas;
}

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