oj.uz

Submission #321446

# Submission time Handle Problem Language Result Execution time Memory
321446 2020-11-12T10:51:52 Z NachoLibre Stations (IOI20_stations) C++14
0 / 100
 816 ms 1120 KB 
#include <bits/stdc++.h>
using namespace std;
#include "stations.h"

const int N = 1003;
vector<int> v[N], dr;
int tn;

void sgd(int dg, int op, int dt) {
	if(dt & 1 ^ 1) dr[dg] = tn, ++tn;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i] != op) {
			sgd(v[dg][i], dg, dt + 1);
		}
	}
	if(dt & 1) dr[dg] = tn, ++tn;
}

vector<int> label(int n, int k, vector<int> x, vector<int> y) {
	for(int i = 0; i < n; ++i) v[i].clear();
	for(int i = 0; i < n - 1; ++i) {
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	dr.clear();
	for(int i = 0; i < n; ++i) dr.push_back(0);
	tn = 0;
	sgd(0, -1, 0);
	return dr;
}

int find_next_station(int a, int b, vector<int> v) {
	int n = v.size();
	for(int i = 0; i < n; ++i) if(v[i] == b) return b;
	if(a == 0) {
		sort(v.begin(), v.end());
		for(int i = 0; i < n; ++i) {
			if(b <= v[i]) return v[i];
		}
		assert(0);
	} else if(v[0] > a) {
		sort(v.begin(), v.end());
		if(b < a) return v[n - 1];
		for(int i = 0; i < n - 1; ++i) {
			if(b <= v[i]) return v[i];
		}
		return v[n - 1];
	} else {
		sort(v.begin(), v.end());
		v.push_back(v[0]);
		for(int i = 0; i < n; ++i) v[i] = v[i + 1];
		v.pop_back();
		if(b <= v[n - 1]) return v[n - 1];
		if(b > a) return v[n - 1];
		for(int i = 1; i < n - 1; ++i) {
			if(b < v[i]) return v[i - 1];
		}
		return v[n - 2];
	}
}

// int main() {
// 	ios::sync_with_stdio(0);
// 	cin.tie(0);
// 	dr = label(5, 4, {0, 1, 1, 2}, {1, 2, 3, 4});
// 	// cout << find_next_station(dr[2], dr[0], {dr[1], dr[4]}) << " --> " << dr[1] << endl;
// 	// cout << find_next_station(dr[1], dr[3], {dr[3], dr[2], dr[0]}) << " --> " << dr[3] << endl;
// 	cout << find_next_station(dr[4], dr[3], {dr[2]}) << " --> " << dr[2] << endl;
// 	return 0;
// }

Compilation message

stations.cpp: In function 'void sgd(int, int, int)':
stations.cpp:10:8: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   10 |  if(dt & 1 ^ 1) dr[dg] = tn, ++tn;
      |     ~~~^~~
stations.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 748 KB Output is correct
2 Correct 652 ms 928 KB Output is correct
3 Incorrect 574 ms 1024 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

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