oj.uz

Submission #825542

# Submission time Handle Problem Language Result Execution time Memory
825542 2023-08-15T02:26:25 Z Edu175 Stations (IOI20_stations) C++17
100 / 100
 798 ms 828 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto dfh:v)cout<<dfh<<" ";cout<<"\n"
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
const ll MAXN=1005;

vector<ll>g[MAXN];
ll /*c[MAXN],*/t[MAXN];
ll cnt=0;
void dfs(ll x, ll f, ll b){
	//c[x]=b;
	if(!b)t[x]=cnt++;
	for(auto y:g[x])if(y!=f)dfs(y,x,b^1);
	if(b)t[x]=cnt++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	fore(i,0,n){
		g[i].clear();
		t[i]=0;
	}
	cnt=0;
	fore(i,0,SZ(u)){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	dfs(0,-1,1);
	vector<ll>res(n);
	fore(i,0,n)res[i]=t[i];
	return res;
}
int find_next_station(int s, int t, vector<int> v){
	ll c=0;
	for(auto i:v)if(i<s)c=1;
	if(!c){
		ll f=s;
		for(auto i:v)f=max(f,i);
		if(t<s)return f;
		for(auto i:v)if(t<=i)return i;
		return v.back();
	}
	else {
		ll f=s;
		for(auto i:v)f=min(f,i);
		if(t>s)return f;
		reverse(ALL(v));
		for(auto i:v)if(t>=i)return i;
		return v.back();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 532 KB Output is correct
2 Correct 421 ms 656 KB Output is correct
3 Correct 576 ms 420 KB Output is correct
4 Correct 557 ms 532 KB Output is correct
5 Correct 467 ms 416 KB Output is correct
6 Correct 313 ms 544 KB Output is correct
7 Correct 417 ms 528 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 536 KB Output is correct
2 Correct 381 ms 540 KB Output is correct
3 Correct 772 ms 416 KB Output is correct
4 Correct 494 ms 528 KB Output is correct
5 Correct 398 ms 532 KB Output is correct
6 Correct 352 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 548 KB Output is correct
2 Correct 294 ms 544 KB Output is correct
3 Correct 625 ms 484 KB Output is correct
4 Correct 457 ms 536 KB Output is correct
5 Correct 374 ms 420 KB Output is correct
6 Correct 343 ms 548 KB Output is correct
7 Correct 344 ms 548 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 467 ms 416 KB Output is correct
12 Correct 396 ms 660 KB Output is correct
13 Correct 410 ms 644 KB Output is correct
14 Correct 296 ms 528 KB Output is correct
15 Correct 31 ms 492 KB Output is correct
16 Correct 57 ms 548 KB Output is correct
17 Correct 98 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 520 KB Output is correct
2 Correct 630 ms 532 KB Output is correct
3 Correct 406 ms 536 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 484 ms 420 KB Output is correct
8 Correct 672 ms 516 KB Output is correct
9 Correct 412 ms 528 KB Output is correct
10 Correct 413 ms 532 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 1 ms 540 KB Output is correct
16 Correct 414 ms 528 KB Output is correct
17 Correct 403 ms 528 KB Output is correct
18 Correct 401 ms 528 KB Output is correct
19 Correct 364 ms 560 KB Output is correct
20 Correct 427 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 660 KB Output is correct
2 Correct 392 ms 528 KB Output is correct
3 Correct 798 ms 432 KB Output is correct
4 Correct 571 ms 424 KB Output is correct
5 Correct 559 ms 420 KB Output is correct
6 Correct 449 ms 520 KB Output is correct
7 Correct 471 ms 532 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 286 ms 544 KB Output is correct
12 Correct 467 ms 544 KB Output is correct
13 Correct 784 ms 528 KB Output is correct
14 Correct 509 ms 536 KB Output is correct
15 Correct 381 ms 544 KB Output is correct
16 Correct 345 ms 540 KB Output is correct
17 Correct 547 ms 528 KB Output is correct
18 Correct 409 ms 636 KB Output is correct
19 Correct 316 ms 780 KB Output is correct
20 Correct 277 ms 532 KB Output is correct
21 Correct 51 ms 620 KB Output is correct
22 Correct 56 ms 600 KB Output is correct
23 Correct 71 ms 660 KB Output is correct
24 Correct 4 ms 488 KB Output is correct
25 Correct 2 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 0 ms 492 KB Output is correct
29 Correct 410 ms 572 KB Output is correct
30 Correct 434 ms 532 KB Output is correct
31 Correct 384 ms 420 KB Output is correct
32 Correct 413 ms 416 KB Output is correct
33 Correct 494 ms 420 KB Output is correct
34 Correct 229 ms 544 KB Output is correct
35 Correct 355 ms 784 KB Output is correct
36 Correct 276 ms 624 KB Output is correct
37 Correct 307 ms 532 KB Output is correct
38 Correct 315 ms 540 KB Output is correct
39 Correct 369 ms 648 KB Output is correct
40 Correct 372 ms 744 KB Output is correct
41 Correct 327 ms 828 KB Output is correct
42 Correct 55 ms 540 KB Output is correct
43 Correct 92 ms 664 KB Output is correct
44 Correct 80 ms 556 KB Output is correct
45 Correct 131 ms 596 KB Output is correct
46 Correct 273 ms 532 KB Output is correct
47 Correct 208 ms 532 KB Output is correct
48 Correct 37 ms 700 KB Output is correct
49 Correct 36 ms 740 KB Output is correct