oj.uz

Submission #933165

# Submission time Handle Problem Language Result Execution time Memory
933165 2024-02-25T07:38:50 Z thunopro Stations (IOI20_stations) C++14
5 / 100
 524 ms 72120 KB 
#include<bits/stdc++.h>
#include "stations.h"
using namespace std ; 
#define maxn 1000009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

//vi label ( int N , int K , vi U , vi V ) ; 
//int find_next_station ( int s , int t , int c ) ; 
//
//int main () 
//{
//	ios_base::sync_with_stdio(0); 
//	cin.tie(0);cout.tie(0); 
//	rf () ; 
//	int n , k ; 
//	vi u , v ; 
//	cin >> n >> k ; 
//	for ( int i = 0 ; i < n-1 ; i ++ ) 
//	{
//		int _u , _v ; cin >> _u >> _v ; 
//		u . pb (_u) , v . pb (_v) ; 
//	}
//	vi res = label (n,k,u,v) ; 
//}

vi adjList [maxn] ; 
int n , k ; 

vi label ( int N , int K , vi U , vi V ) 
{
	for ( int i = 0 ; i < n ; i ++ ) adjList [i] . clear () ; 
	n = N , k = K ; 
	for ( int i = 0 ; i < n-1 ; i ++ ) 
	{
		adjList [U[i]] . pb (V[i]) ; 
		adjList [V[i]] . pb (U[i]) ; 
	}
	int root = -1 ; 
	for ( int i = 0 ; i < n ; i ++ ) if ( adjList [i].size () == 1 ) root = i ; 
	vi res(n,-1) ; 
	int num = 0 ; 
	stack <int> q ; 
	q . push (root) ; 
	while ( q.size () ) 
	{
		int u = q.top() ; q.pop() ; res [u] = num ++ ;
		for ( auto v : adjList [u] ) if ( res [v] == -1 ) q . push (v) ; 
	}
	return res ; 
}

int find_next_station ( int s , int t , vi c ) 
{
	for ( auto x : c ) 
	{
		if ( s <= x && x <= t ) return x ; 
		if ( s >= x && x >= t ) return x ; 
	}
}

Compilation message

stations.cpp: In function 'void rf()':
stations.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 48096 KB Output is correct
2 Correct 302 ms 47904 KB Output is correct
3 Correct 512 ms 47788 KB Output is correct
4 Correct 423 ms 48044 KB Output is correct
5 Correct 325 ms 47788 KB Output is correct
6 Correct 254 ms 47868 KB Output is correct
7 Correct 270 ms 47788 KB Output is correct
8 Correct 12 ms 47872 KB Output is correct
9 Correct 16 ms 48124 KB Output is correct
10 Correct 10 ms 47872 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 72120 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 47876 KB Output is correct
2 Correct 282 ms 47880 KB Output is correct
3 Correct 521 ms 47788 KB Output is correct
4 Correct 387 ms 47788 KB Output is correct
5 Correct 321 ms 47788 KB Output is correct
6 Correct 273 ms 48120 KB Output is correct
7 Correct 263 ms 47788 KB Output is correct
8 Correct 11 ms 47868 KB Output is correct
9 Correct 12 ms 47876 KB Output is correct
10 Correct 11 ms 47876 KB Output is correct
11 Runtime error 36 ms 71844 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 47788 KB Output is correct
2 Correct 389 ms 47788 KB Output is correct
3 Correct 349 ms 47788 KB Output is correct
4 Correct 13 ms 47876 KB Output is correct
5 Correct 12 ms 47876 KB Output is correct
6 Correct 11 ms 47876 KB Output is correct
7 Runtime error 27 ms 71852 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 47872 KB Output is correct
2 Correct 290 ms 47872 KB Output is correct
3 Correct 524 ms 47788 KB Output is correct
4 Correct 378 ms 47788 KB Output is correct
5 Correct 350 ms 47788 KB Output is correct
6 Correct 255 ms 47868 KB Output is correct
7 Correct 253 ms 48044 KB Output is correct
8 Correct 12 ms 47884 KB Output is correct
9 Correct 12 ms 47872 KB Output is correct
10 Correct 10 ms 47868 KB Output is correct
11 Runtime error 28 ms 71940 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -