oj.uz

Submission #716496

# Submission time Handle Problem Language Result Execution time Memory
716496 2023-03-30T07:56:24 Z myrcella Stations (IOI20_stations) C++17
100 / 100
 1462 ms 55640 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "stations.h"

int dfs(int u,int pos,int flag,int lst,vector <int> &l,vector <vector<int>> edge) {
	int ret = pos;
	if (flag==1) l[u] = pos++;
	for (int v:edge[u]) {
		if (v==lst) continue;
		int tmp = dfs(v,pos,flag^1,u,l,edge);
		pos += tmp;
	}
	if (flag==0) l[u] = pos++;
//	debug(233),cout<<u<<" "<<l[u]<<endl;
	return pos-ret;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector <int> ans(n);
	vector <vector<int>> edge(n);
	rep(i,0,n-1) {
		edge[u[i]].pb(v[i]);
		edge[v[i]].pb(u[i]);
	}
	dfs(0,0,0,-1,ans,edge);
	return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (SZ(c)==1) return c[0];
	if (c.back()<s) {
		rep(i,1,SZ(c)-1) {
			if (t>=c[i] and t<c[i+1]) return c[i];
		}
		if (t>=c.back() and t<s) return c.back();
		return c[0];
	}
	else {
		assert(c[0]>s);
		if (t>s and t<=c[0]) return c[0];
		rep(i,1,SZ(c)-1) if (t>c[i-1] and t<=c[i]) return c[i];
		return c.back();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 55492 KB Output is correct
2 Correct 950 ms 55096 KB Output is correct
3 Correct 858 ms 416 KB Output is correct
4 Correct 722 ms 416 KB Output is correct
5 Correct 450 ms 508 KB Output is correct
6 Correct 904 ms 49236 KB Output is correct
7 Correct 556 ms 41716 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 0 ms 488 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 1112 KB Output is correct
2 Correct 631 ms 1004 KB Output is correct
3 Correct 790 ms 636 KB Output is correct
4 Correct 632 ms 420 KB Output is correct
5 Correct 500 ms 508 KB Output is correct
6 Correct 517 ms 1128 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 55416 KB Output is correct
2 Correct 817 ms 53044 KB Output is correct
3 Correct 903 ms 420 KB Output is correct
4 Correct 635 ms 416 KB Output is correct
5 Correct 683 ms 504 KB Output is correct
6 Correct 832 ms 53432 KB Output is correct
7 Correct 515 ms 42652 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 593 ms 504 KB Output is correct
12 Correct 828 ms 54504 KB Output is correct
13 Correct 889 ms 50188 KB Output is correct
14 Correct 503 ms 3032 KB Output is correct
15 Correct 60 ms 584 KB Output is correct
16 Correct 180 ms 648 KB Output is correct
17 Correct 538 ms 688 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 416 KB Output is correct
2 Correct 604 ms 416 KB Output is correct
3 Correct 636 ms 508 KB Output is correct
4 Correct 6 ms 420 KB Output is correct
5 Correct 5 ms 472 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 553 ms 420 KB Output is correct
8 Correct 762 ms 484 KB Output is correct
9 Correct 640 ms 416 KB Output is correct
10 Correct 428 ms 508 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 389 ms 504 KB Output is correct
17 Correct 436 ms 420 KB Output is correct
18 Correct 508 ms 508 KB Output is correct
19 Correct 510 ms 512 KB Output is correct
20 Correct 519 ms 512 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 55400 KB Output is correct
2 Correct 923 ms 48876 KB Output is correct
3 Correct 882 ms 420 KB Output is correct
4 Correct 700 ms 416 KB Output is correct
5 Correct 548 ms 500 KB Output is correct
6 Correct 808 ms 55396 KB Output is correct
7 Correct 546 ms 31224 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 781 ms 1104 KB Output is correct
12 Correct 578 ms 1136 KB Output is correct
13 Correct 860 ms 416 KB Output is correct
14 Correct 638 ms 420 KB Output is correct
15 Correct 582 ms 416 KB Output is correct
16 Correct 466 ms 1012 KB Output is correct
17 Correct 497 ms 416 KB Output is correct
18 Correct 816 ms 37284 KB Output is correct
19 Correct 919 ms 51692 KB Output is correct
20 Correct 518 ms 4188 KB Output is correct
21 Correct 71 ms 472 KB Output is correct
22 Correct 173 ms 612 KB Output is correct
23 Correct 471 ms 740 KB Output is correct
24 Correct 6 ms 488 KB Output is correct
25 Correct 5 ms 492 KB Output is correct
26 Correct 3 ms 500 KB Output is correct
27 Correct 3 ms 500 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 516 ms 420 KB Output is correct
30 Correct 487 ms 420 KB Output is correct
31 Correct 489 ms 548 KB Output is correct
32 Correct 543 ms 420 KB Output is correct
33 Correct 614 ms 416 KB Output is correct
34 Correct 763 ms 42080 KB Output is correct
35 Correct 1035 ms 55640 KB Output is correct
36 Correct 1462 ms 45764 KB Output is correct
37 Correct 999 ms 13532 KB Output is correct
38 Correct 903 ms 13472 KB Output is correct
39 Correct 847 ms 17748 KB Output is correct
40 Correct 881 ms 17840 KB Output is correct
41 Correct 905 ms 14568 KB Output is correct
42 Correct 273 ms 672 KB Output is correct
43 Correct 458 ms 676 KB Output is correct
44 Correct 470 ms 1052 KB Output is correct
45 Correct 595 ms 1568 KB Output is correct
46 Correct 546 ms 13832 KB Output is correct
47 Correct 768 ms 26764 KB Output is correct
48 Correct 390 ms 1140 KB Output is correct
49 Correct 472 ms 1240 KB Output is correct