Submission #622585

#TimeUsernameProblemLanguageResultExecution timeMemory
622585erekleStations (IOI20_stations)C++17
76 / 100
852 ms756 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> g; vector<int> tin, tout, depth; int t; void dfs(int node, int parent = -1) { if (parent == -1) depth[node] = 0; else depth[node] = depth[parent] + 1; tin[node] = ++t; for (int child : g[node]) { if (child != parent) dfs(child, node); } tout[node] = ++t; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { g.clear(), tin.clear(), tout.clear(), depth.clear(); g.resize(n); for (int i = 0; i < u.size(); ++i) { g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } t = -1; tin.resize(n), tout.resize(n); depth.resize(n); dfs(0); vector<int> labels(n); for (int i = 0; i < n; i++) { if (depth[i] & 1) labels[i] = tout[i]; else labels[i] = tin[i]; } return labels; } int find_next_station(int s, int t, vector<int> c) { int m = c.size(); if (m == 1) return c[0]; sort(c.begin(), c.end()); if (s < c.front()) { // s has tin, rest have tout // c.back() is parent of s if (s <= t && t <= c[m-2]) { // t is in subtree of s // which child for (int x : c) { if (t <= x) return x; } } else { // t is not in subtree of s return c.back(); } } else { // s has tout, rest have tin // c.front() is parent of s if (c[1] <= t && t <= s) { // t is in subtree of s // which child for (int i = m-1; i >= 0; --i) { if (t >= c[i]) return c[i]; } } else { // t is not in subtree of s return c.front(); } } }

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < u.size(); ++i) {
      |                  ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...