oj.uz

Submission #826696

# Submission time Handle Problem Language Result Execution time Memory
826696 2023-08-15T21:06:00 Z sadsa Stations (IOI20_stations) C++17
5 / 100
 818 ms 676 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using vvl = vector<vl>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

void dfs(int pos, int prv, int &lbl, const vvi &adj, vi &labels) {
	DBG(pos, prv, lbl);
	labels[pos] = lbl;
	++lbl;
	if (adj[pos].size() == 1) return;
	
	for (int nxt : adj[pos]) {
		if (nxt != prv) {
			dfs(nxt, pos, lbl, adj, labels);
		}
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vi labels(n);

	vvi adj(n);
	for (int i = 0; i < n-1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	DBG(u);
	DBG(v);
	DBG(adj);

	int root = 0, prv = -1;
	while (adj[root].size() != 1) {
		for (int nxt : adj[root]) {
			if (nxt != prv) {
				prv = root;
				root = nxt;
				break;
			}
		}
	}

	DBG(root);

	labels[root] = 0;
	int lbl = 1;
	dfs(adj[root][0], root, lbl, adj, labels);
	DBG(labels);

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	DBG(s, t, c);
	if (c.size() == 1 || t < s) return c[0];
	return *(upper_bound(RANGE(c), t)-1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 636 KB Output is correct
2 Correct 323 ms 544 KB Output is correct
3 Correct 818 ms 568 KB Output is correct
4 Correct 596 ms 508 KB Output is correct
5 Correct 392 ms 504 KB Output is correct
6 Correct 364 ms 632 KB Output is correct
7 Correct 318 ms 632 KB Output is correct
8 Correct 2 ms 488 KB Output is correct
9 Correct 1 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 456 ms 504 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 544 KB Output is correct
2 Correct 412 ms 672 KB Output is correct
3 Correct 665 ms 416 KB Output is correct
4 Correct 441 ms 500 KB Output is correct
5 Correct 458 ms 416 KB Output is correct
6 Correct 309 ms 548 KB Output is correct
7 Correct 430 ms 548 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 414 ms 500 KB Output is correct
12 Incorrect 431 ms 676 KB Wrong query response.
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 500 KB Output is correct
2 Correct 524 ms 544 KB Output is correct
3 Correct 421 ms 420 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 476 ms 508 KB Output is correct
8 Correct 725 ms 420 KB Output is correct
9 Correct 590 ms 416 KB Output is correct
10 Correct 469 ms 512 KB Output is correct
11 Incorrect 2 ms 492 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 544 KB Output is correct
2 Correct 382 ms 544 KB Output is correct
3 Correct 688 ms 420 KB Output is correct
4 Correct 562 ms 572 KB Output is correct
5 Correct 471 ms 416 KB Output is correct
6 Correct 314 ms 656 KB Output is correct
7 Correct 301 ms 632 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Incorrect 286 ms 548 KB Wrong query response.
12 Halted 0 ms 0 KB -