oj.uz

답안 #361983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361983 2021-02-01T13:57:15 Z ryansee 기지국 (IOI20_stations) C++14
76 / 100
 1083 ms 1288 KB 
#include "stations.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
 
using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 
 
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
 
vector<int> label(int n, int k, vector<int> U, vector<int> V) {
	vector<vector<int>> v(n, vector<int>());
	FOR(i,0,n-2) v[U[i]].eb(V[i]), v[V[i]].eb(U[i]);
	vector<int> st(n, 0), en(n, 0);
	int co = 0;
	function<void(int,int)>dfs=[&](int x,int p){
		st[x]=co++;
		for(auto i:v[x]) if(i^p) dfs(i, x);
		en[x]=co++;
	};
	dfs(0, 0);
	vector<int> C(n);
	function<void(int,int,int)>dfs2=[&](int x,int p,int co){
		if(co == 0) C[x] = st[x];
		else C[x] = en[x];
		for(auto i:v[x]) if(i^p) dfs2(i, x, !co);
	};
	dfs2(0, 0, 0);
	return C;
}
int find_next_station(int S, int T, vector<int> c) {
	if(siz(c) == 1) return c[0];
	if(S == 0) {
		for(auto i:c) if(i >= T) return i;
		assert(0);
	}
	int pre, post, b;
	if(c[0] < S) { // S is post order
		post = S, pre = c[1] - 1, b = 1;
	} else { // S is pre
		pre = S, post = c[siz(c)-2] + 1, b = 0;
	}
	if(pre <= T && T <= post) { // in subtree
		if(b==0) {
			for(auto i:c) if(i >= T) return i;
			assert(0);
		} else {
			reverse(all(c));
			for(auto i:c) if(i <= T) return i;
			assert(0);
		}
	} else {
		if(b) return c[0];
		else return c.back();
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 492 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 468 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 864 KB Output is correct
2 Correct 550 ms 1012 KB Output is correct
3 Correct 1083 ms 864 KB Output is correct
4 Correct 784 ms 864 KB Output is correct
5 Correct 674 ms 864 KB Output is correct
6 Correct 537 ms 884 KB Output is correct
7 Correct 579 ms 968 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 2 ms 788 KB Output is correct
11 Correct 678 ms 864 KB Output is correct
12 Correct 580 ms 1000 KB Output is correct
13 Correct 589 ms 864 KB Output is correct
14 Correct 484 ms 780 KB Output is correct
15 Correct 53 ms 856 KB Output is correct
16 Correct 71 ms 812 KB Output is correct
17 Correct 114 ms 772 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 912 ms 736 KB Output is correct
2 Correct 715 ms 756 KB Output is correct
3 Correct 615 ms 756 KB Output is correct
4 Correct 2 ms 912 KB Output is correct
5 Correct 5 ms 872 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 622 ms 864 KB Output is correct
8 Correct 994 ms 864 KB Output is correct
9 Correct 724 ms 864 KB Output is correct
10 Correct 629 ms 884 KB Output is correct
11 Correct 7 ms 872 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 5 ms 864 KB Output is correct
14 Correct 4 ms 872 KB Output is correct
15 Correct 2 ms 872 KB Output is correct
16 Correct 515 ms 864 KB Output is correct
17 Correct 579 ms 736 KB Output is correct
18 Correct 564 ms 980 KB Output is correct
19 Correct 537 ms 864 KB Output is correct
20 Correct 614 ms 756 KB Output is correct

Subtask #5
50.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 588 ms 920 KB Partially correct
2 Partially correct 474 ms 904 KB Partially correct
3 Correct 901 ms 1128 KB Output is correct
4 Correct 704 ms 1140 KB Output is correct
5 Correct 624 ms 736 KB Output is correct
6 Partially correct 461 ms 928 KB Partially correct
7 Partially correct 522 ms 1288 KB Partially correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Partially correct 516 ms 860 KB Partially correct
12 Partially correct 582 ms 896 KB Partially correct
13 Correct 1047 ms 864 KB Output is correct
14 Correct 923 ms 756 KB Output is correct
15 Correct 788 ms 872 KB Output is correct
16 Partially correct 532 ms 884 KB Partially correct
17 Correct 653 ms 1184 KB Output is correct
18 Partially correct 669 ms 1140 KB Partially correct
19 Partially correct 494 ms 1164 KB Partially correct
20 Partially correct 527 ms 756 KB Partially correct
21 Correct 52 ms 736 KB Output is correct
22 Partially correct 76 ms 756 KB Partially correct
23 Partially correct 113 ms 848 KB Partially correct
24 Correct 5 ms 864 KB Output is correct
25 Correct 5 ms 756 KB Output is correct
26 Correct 6 ms 884 KB Output is correct
27 Correct 5 ms 544 KB Output is correct
28 Correct 2 ms 1028 KB Output is correct
29 Correct 594 ms 884 KB Output is correct
30 Correct 573 ms 756 KB Output is correct
31 Correct 571 ms 756 KB Output is correct
32 Correct 522 ms 884 KB Output is correct
33 Correct 653 ms 756 KB Output is correct
34 Partially correct 330 ms 884 KB Partially correct
35 Partially correct 500 ms 884 KB Partially correct
36 Partially correct 509 ms 1012 KB Partially correct
37 Partially correct 582 ms 972 KB Partially correct
38 Partially correct 500 ms 1216 KB Partially correct
39 Partially correct 498 ms 1144 KB Partially correct
40 Partially correct 587 ms 1044 KB Partially correct
41 Partially correct 451 ms 992 KB Partially correct
42 Partially correct 61 ms 804 KB Partially correct
43 Partially correct 126 ms 1064 KB Partially correct
44 Partially correct 153 ms 736 KB Partially correct
45 Partially correct 217 ms 992 KB Partially correct
46 Partially correct 348 ms 756 KB Partially correct
47 Partially correct 360 ms 884 KB Partially correct
48 Partially correct 78 ms 880 KB Partially correct
49 Partially correct 74 ms 828 KB Partially correct