oj.uz

Submission #1096592

# Submission time Handle Problem Language Result Execution time Memory
1096592 2024-10-04T20:57:35 Z Doncho_Bonboncho Game (APIO22_game) C++17
0 / 100
 9 ms 23896 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Incorrect 9 ms 23896 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Incorrect 9 ms 23896 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Incorrect 9 ms 23896 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Incorrect 9 ms 23896 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Incorrect 9 ms 23896 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -