Submission #781002

#TimeUsernameProblemLanguageResultExecution timeMemory
781002JosiaStations (IOI20_stations)C++17
76 / 100
837 ms752 KiB
#include "stations.h" #include <bits/stdc++.h> using namespace std; vector<int> pre; vector<int> post; vector<vector<int>> graph; vector<int> depth; int tim; void dfs(int v, int d) { if (pre[v] != -1) return; pre[v] = tim++; depth[v] = d; for (int i: graph[v]) { dfs(i, d+1); } post[v] = tim++; } vector<int> label(int n, int k, vector<int> u, vector<int> v) { tim = 0; pre.assign(n, -1); post.assign(n, -1); depth.assign(n, -1); graph.clear(); graph.resize(n); for (int i = 0; i<n-1; i++) { graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } dfs(0, 0); // for (int i: pre) cerr << i << " "; // cerr << "\n"; vector<int> labels(n); for (int i=0; i<n; i++) { if (depth[i]%2) labels[i] = pre[i]; else labels[i] = post[i]; } return labels; } int find_next_station(int s, int t, vector<int> c) { if (c.size() == 1) return c[0]; sort(c.begin(), c.end()); bool bound = s > c[0]; // 0 lower; 1 higher if (bound == 0) { if (t < s) return c.back(); if (t > *prev(c.end())) return c.back(); for (int i = 1; i<c.size(); i++) { if (t > c[i-1] && t <= c[i]) return c[i]; } return c[0]; } else { if (t > s) return c[0]; if (t < c[1]) return c[0]; for (int i = 0; i<c.size()-1; i++) { if (t < c[i+1] && t >= c[i]) return c[i]; } return c.back(); } }

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 1; i<c.size(); i++) {
      |                         ~^~~~~~~~~
stations.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i<c.size()-1; i++) {
      |                         ~^~~~~~~~~~~
#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...