oj.uz

Submission #361829

# Submission time Handle Problem Language Result Execution time Memory
361829 2021-01-31T17:45:28 Z ryansee Stations (IOI20_stations) C++14
36.2303 / 100
 1020 ms 1172 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-1;
	};
	dfs(0, 0);
	vector<int> C(n);
	FOR(i,0,n-1) { //(pre, post)
		C[i] = st[i] + (en[i] << 10);
	}
	return C;
}
int pre(int x) {
	return x & ((1<<10) - 1);
}
int post(int x) {
	return (x >> 10);
}
int find_next_station(int S, int T, vector<int> c) {
	int s[2] = {pre(S), post(S)};
	int t[2] = {pre(T), post(T)};
	if(t[0] <= s[0] && t[1] >= s[1]) { // t is part of s
		for(auto i:c) if(pre(i) < s[0]) return i;
	} else if(s[0] <= t[0] && s[1] >= t[1]) {
		for(auto i:c) if(pre(i) <= t[0] && post(i) >= t[1] && pre(i) > s[0]) {
			return i;
		}
	} else {
		for(auto i:c) if(pre(i) < s[0]) return i;
	}
	assert(0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9216
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 364 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1018880
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=0, label=1019904
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 756 KB Output is correct
2 Correct 682 ms 864 KB Output is correct
3 Correct 626 ms 864 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 615 ms 736 KB Output is correct
8 Correct 971 ms 736 KB Output is correct
9 Correct 839 ms 756 KB Output is correct
10 Correct 627 ms 864 KB Output is correct
11 Correct 7 ms 864 KB Output is correct
12 Correct 7 ms 872 KB Output is correct
13 Correct 5 ms 992 KB Output is correct
14 Correct 5 ms 872 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 518 ms 736 KB Output is correct
17 Correct 531 ms 864 KB Output is correct
18 Correct 487 ms 756 KB Output is correct
19 Correct 605 ms 756 KB Output is correct
20 Correct 628 ms 864 KB Output is correct

Subtask #5
26.2303 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 631 ms 944 KB Partially correct
2 Partially correct 498 ms 1024 KB Partially correct
3 Partially correct 1020 ms 884 KB Partially correct
4 Partially correct 690 ms 756 KB Partially correct
5 Partially correct 676 ms 756 KB Partially correct
6 Partially correct 511 ms 948 KB Partially correct
7 Partially correct 445 ms 1012 KB Partially correct
8 Partially correct 3 ms 756 KB Partially correct
9 Partially correct 4 ms 912 KB Partially correct
10 Partially correct 1 ms 756 KB Partially correct
11 Partially correct 512 ms 780 KB Partially correct
12 Partially correct 646 ms 772 KB Partially correct
13 Partially correct 984 ms 756 KB Partially correct
14 Partially correct 773 ms 756 KB Partially correct
15 Partially correct 746 ms 864 KB Partially correct
16 Partially correct 481 ms 736 KB Partially correct
17 Partially correct 659 ms 756 KB Partially correct
18 Partially correct 506 ms 992 KB Partially correct
19 Partially correct 544 ms 992 KB Partially correct
20 Partially correct 443 ms 784 KB Partially correct
21 Partially correct 58 ms 756 KB Partially correct
22 Partially correct 73 ms 736 KB Partially correct
23 Partially correct 108 ms 736 KB Partially correct
24 Partially correct 5 ms 1000 KB Partially correct
25 Partially correct 6 ms 736 KB Partially correct
26 Partially correct 6 ms 756 KB Partially correct
27 Partially correct 5 ms 736 KB Partially correct
28 Partially correct 2 ms 912 KB Partially correct
29 Partially correct 560 ms 864 KB Partially correct
30 Partially correct 528 ms 756 KB Partially correct
31 Partially correct 566 ms 768 KB Partially correct
32 Partially correct 633 ms 864 KB Partially correct
33 Partially correct 624 ms 864 KB Partially correct
34 Partially correct 329 ms 968 KB Partially correct
35 Partially correct 504 ms 884 KB Partially correct
36 Partially correct 488 ms 960 KB Partially correct
37 Partially correct 471 ms 1112 KB Partially correct
38 Partially correct 518 ms 1016 KB Partially correct
39 Partially correct 484 ms 992 KB Partially correct
40 Partially correct 432 ms 884 KB Partially correct
41 Partially correct 525 ms 1172 KB Partially correct
42 Partially correct 74 ms 796 KB Partially correct
43 Partially correct 124 ms 756 KB Partially correct
44 Partially correct 180 ms 736 KB Partially correct
45 Partially correct 182 ms 780 KB Partially correct
46 Partially correct 315 ms 768 KB Partially correct
47 Partially correct 336 ms 996 KB Partially correct
48 Partially correct 68 ms 880 KB Partially correct
49 Partially correct 77 ms 864 KB Partially correct