oj.uz

Submission #361758

# Submission time Handle Problem Language Result Execution time Memory
361758 2021-01-31T14:21:47 Z ryansee Stations (IOI20_stations) C++14
16 / 100
 1218 ms 1068 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> C(n, 0);
	int r = 0;
	FOR(i,0,n-1) if(siz(v[i]) > siz(v[r])) r = i;
	function<void(int,int,int)>dfs=[&](int x,int p,int co) {
		C[x] = co;
		for(auto i:v[x]) if(i^p) dfs(i, x, co + 1);
	};
	C[r] = 1e6;
	ll co = 0;
	for(auto i:v[r]) dfs(i, r, co), co += 1000;
	return C;
}

int find_next_station(int s, int t, vector<int> c) {
	if(s == 1e6) {
		int target = t / 1000 * 1000;
		assert(find(all(c), target) != c.end());
		return target;
	} else {
		if(s / 1000 == t / 1000) {
			if(s > t) return *min_element(all(c));
			else {
				if(find(all(c), int(1e6)) != c.end()) c.erase(find(all(c), int(1e6)));
				return *max_element(all(c));
			}
		} else {
			if(find(all(c), int(1e6)) != c.end()) return int(1e6);
			return *min_element(all(c));
		}
	}
}

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=1000000
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=1, label=1000000
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 884 KB Output is correct
2 Correct 499 ms 1012 KB Output is correct
3 Correct 1018 ms 884 KB Output is correct
4 Correct 794 ms 736 KB Output is correct
5 Correct 753 ms 736 KB Output is correct
6 Correct 518 ms 1000 KB Output is correct
7 Correct 463 ms 884 KB Output is correct
8 Correct 4 ms 736 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 650 ms 884 KB Output is correct
12 Correct 589 ms 1068 KB Output is correct
13 Correct 489 ms 1044 KB Output is correct
14 Correct 593 ms 792 KB Output is correct
15 Correct 57 ms 856 KB Output is correct
16 Correct 68 ms 736 KB Output is correct
17 Correct 108 ms 756 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 756 KB Output is correct
2 Correct 639 ms 864 KB Output is correct
3 Correct 659 ms 872 KB Output is correct
4 Correct 3 ms 776 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 545 ms 736 KB Output is correct
8 Correct 979 ms 1000 KB Output is correct
9 Correct 687 ms 864 KB Output is correct
10 Correct 602 ms 864 KB Output is correct
11 Incorrect 1 ms 364 KB Invalid labels (duplicates values). scenario=5, label=1
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 557 ms 952 KB Partially correct
2 Partially correct 481 ms 864 KB Partially correct
3 Partially correct 905 ms 756 KB Partially correct
4 Partially correct 649 ms 992 KB Partially correct
5 Partially correct 609 ms 864 KB Partially correct
6 Partially correct 435 ms 884 KB Partially correct
7 Partially correct 495 ms 884 KB Partially correct
8 Partially correct 2 ms 872 KB Partially correct
9 Partially correct 5 ms 736 KB Partially correct
10 Partially correct 2 ms 864 KB Partially correct
11 Incorrect 5 ms 364 KB Invalid labels (duplicates values). scenario=0, label=2
12 Halted 0 ms 0 KB -