Submission #593967

#	Time	Username	Problem	Language	Result	Execution time	Memory
593967		Clan328	Stations (IOI20_stations)	C++17	0 / 100	830 ms	688 KiB

stations

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
	for (auto elem : v) 
		stream << elem << " ";
	return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
		stream >> elem;
   return stream;
}

void settings() {
	#ifdef LOCAL
		freopen("io/input.txt", "r", stdin);
		freopen("io/output.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0);
	cin.tie(0);
}

int tmpD;
vi visited, res;
vvi G;

void dfs(int v, int val) {
	visited[v] = true;
	res[v] = val;
	int idx = 1;
	for (auto u : G[v]) {
		if (visited[u]) continue;
		dfs(u, val*tmpD+idx);
		idx++;
	}
}

vi label(int n, int k, std::vector<int> u, std::vector<int> v) {
	res = vi(n);
	vi deg(n);
	G = vvi(n);
	visited = vi(n);
	for (int i = 0; i < u.size(); i++) {
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
		deg[u[i]]++;
		deg[v[i]]++;
	}

	int maxDeg = 0;
	for (int i = 1; i < n; i++) if (deg[i] > deg[maxDeg]) maxDeg = i;

	int x = -1;
	// for (int i = 0; i < n; i++) {
	// 	if (deg[i] < deg[maxDeg]) {
	// 		if (x == -1) x = i;
	// 		else if (deg[x] < deg[i]) x = i;
	// 	}
	// }

	// if (x == -1) x = 0;
	
	x = maxDeg;
	tmpD = deg[x];
	dfs(x, 0);
	// cout << res << nL;
	return res;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (c.size() == 1) return c[0];

	int d;
	cout << s << nL;
	if (s == 0) d = c[c.size()-1];
	else d = (c[1]-1)/s;
	while (t > s) {
		if ((t-1)/d == s) return t;
		t = (t-1)/d;
	}
	return (s-1)/d;
}

Compilation message (stderr)

stations.cpp: In function 'vi label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

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