Submission #560465

#	Time	Username	Problem	Language	Result	Execution time	Memory
560465		AlperenT	Stations (IOI20_stations)	C++17	57.32 / 100	831 ms	832 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;

int t, tin[N], tout[N];
vector<int> tree[N], labels;

void dfs1(int v, int p, int x){
	labels[v] = x;

	for(auto e : tree[v]){
		if(e != p) dfs1(e, v, x + 1);
	}
}

void dfsgood(int v, int p){
	tin[v] = ++t;

	for(auto e : tree[v]){
		if(e != p) dfsgood(e, v);
	}

	tout[v] = t;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	labels.assign(n, -1);

	for(int i = 0; i < n; i++) tree[i].clear(), tin[i] = tout[i] = 0;

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

	if(k == 1000){    // subtask 1, 2
		int mx = 0;

		for(int i = 0; i < n; i++) mx = max(mx, (int)tree[i].size());

		if(mx <= 2){    // subtask 1
			for(int i = 0; i < n; i++){
				if(tree[i].size() == 1){
					dfs1(i, -1, 0);
					break;
				}
			}
		}
		else{    // subtask 2
			for(int i = 0; i < n; i++) labels[i] = i;
		}
	}
	else{    // subtask 3, 4, 5
		t = -1;
		dfsgood(0, -1);

		for(int i = 0; i < n; i++) labels[i] = tout[i] * 1000 + tin[i];
	}

	return labels;
}

bool ispar(int ain, int aout, int bin, int bout){
	if(bin >= ain && bout <= aout) return true;
	else return false;
}

int find_next_station(int s, int t, vector<int> c){
	if(c.size() == 1) return c[0];
	else{
		if(c.size() == 2 && s < 1000 && c[0] == s - 1 && c[1] == s + 1){    // subtask 1
			if(t < s) return c[0];
			else return c[1];
		}
		else if(s < 1000){    // subtask 2
			int p, l, r;

			if(s == 0) l = c[0], r = c[1];
			else p = c[0], l = c[1], r = c.size() == 3 ? c[2] : -1;

			if(t < s) return p;
			else{
				while(t > 0){
					if((t - 1) / 2 == l) return l;
					else if(r != -1 && (t - 1) / 2 == r) return r;

					t = (t - 1) / 2;
				}

				return p;
			}
		}
		else{    // subtask 3, 4, 5
			int ssin, ssout, ttin, ttout;

			ssin = s % 1000, ssout = s / 1000, ttin = t % 1000, ttout = t / 1000;

			vector<int> tin(c.size(), 0), tout(c.size(), 0);

			for(int i = 0; i < c.size(); i++) tin[i] = c[i] % 1000, tout[i] = c[i] / 1000;

			for(int i = 0; i < c.size(); i++){
				if(!ispar(tin[i], tout[i], ssin, ssout) && ispar(tin[i], tout[i], ttin, ttout)) return c[i];
			}

			for(int i = 0; i < c.size(); i++){
				if(ispar(tin[i], tout[i], ssin, ssout)) return c[i];
			}

			return -1;
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int i = 0; i < c.size(); i++) tin[i] = c[i] % 1000, tout[i] = c[i] / 1000;
      |                   ~~^~~~~~~~~~
stations.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for(int i = 0; i < c.size(); i++){
      |                   ~~^~~~~~~~~~
stations.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    for(int i = 0; i < c.size(); i++){
      |                   ~~^~~~~~~~~~
stations.cpp:84:21: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |    if(t < s) return p;
      |                     ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 26.3205 / 61