oj.uz

Submission #388391

# Submission time Handle Problem Language Result Execution time Memory
388391 2021-04-11T09:48:50 Z JimmyZJX Stations (IOI20_stations) C++14
0 / 100
 2 ms 584 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

Vb visited(1003, false);
Vii nbs(1003);
int l = 0;

Vi labels;
void dfs(int x, int mode) { // 0: start, 1: end
	visited[x] = true;
	if (mode == 0) labels[x] = l++;

	for (int nb : nbs[x]) {
		if (visited[nb]) continue;
		dfs(nb, 1 - mode);
	}

	if (mode == 1) labels[x] = l++;
}

Vi label(int n, int k, Vi u, Vi v) {
	forR(i, n - 1) {
		nbs[u[i]].push_back(v[i]);
		nbs[v[i]].push_back(u[i]);
	}

	labels = Vi(n);
	dfs(0, 0);
	assert(l == n);

	return labels;
}

int find_next_station(int s, int t, Vi c) {
	if (s < c[0]) {
		// s.mode == 0
		int start = s;
		for (int end : c) {
			if (t >= start && t <= end) return end;
		}
		return c.back();
	} else {
		// s.mode == 1
		int end = s;
		for (auto it = c.rbegin(); it != c.rend(); it++) {
			int start = *it;
			if (t >= start && t <= end) return start;
		}
		return c[0];
	}
}

#ifdef TEST_LOCAL
int main() {
	auto lbs = label(5, 10, Vi{ 0, 1, 1, 2 }, Vi{ 1, 2, 3, 4 });

	return 0;
}
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 560 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 584 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 576 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -