Submission #605136

#	Time	Username	Problem	Language	Result	Execution time	Memory
605136		gagik_2007	Stations (IOI20_stations)	C++17	36.32 / 100	997 ms	860 KiB

stations

#include "stations.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

ll n;
vector<int>g[1007];
int tin[1507], tout[1507];
int timer = 0;

void dfs(int v, int par = -1) {
	tin[v] = timer++;
	for (int i = 0; i < g[v].size(); i++) {
		int to = g[v][i];
		if (to != par) {
			dfs(to, v);
		}
	}
	tout[v] = timer;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> lbl(n);
	for (int i = 0; i < n - 1; i++) {
		g[v[i]].push_back(u[i]);
		g[u[i]].push_back(v[i]);
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		lbl[i] = tin[i] * 1001 + tout[i];
	}
	for (int i = 0; i < n; i++) {
		tin[i] = 0;
		tout[i] = 0;
		timer = 0;
		g[i].clear();
	}
	return lbl;
}

bool papa(int v, int u) {
	int iv = v / 1001;
	int ov = v % 1001;
	int iu = u / 1001;
	int ou = u % 1001;
	return (iv <= iu && ov >= ou);
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1)return c[0];
	int par = -1;
	for (auto x : c) {
		if (x / 1001 < s / 1001) {
			par = x;
			break;
		}
	}
	if (papa(s, t)) {
		for (auto x : c) {
			if (papa(x, t) && x != par) {
				return x;
			}
		}
	}
	else {
		return par;
	}
}

/*
1
8 1000000
0 1
0 2
1 3
1 4
3 5
3 6
5 7
5
7 2 5
2 3 0
6 5 3
7 4 5
6 4 3
1 8 1000 0 1 0 2 1 3 1 4 3 5 3 6 5 7 5 7 2 5 2 3 0 6 5 3 7 4 5 6 4 3
1 8 1000000
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5
7 2 3
1 7 3
2 5 5
0 5 2
5 0 2
*/

Compilation message (stderr)

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < g[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^

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