Submission #1060547

#TimeUsernameProblemLanguageResultExecution timeMemory
1060547ArthuroWichStations (IOI20_stations)C++17
100 / 100
629 ms1444 KiB
#include "stations.h" #include<bits/stdc++.h> using namespace std; vector<int> adj[1005]; int timer = 0, st[1005], en[1005], l[1005]; void dfs(int i, int p, int d) { st[i] = timer; timer++; if (d % 2 == 0) { l[i] = st[i]; } for (int j : adj[i]) { if (j == p) { continue; } dfs(j, i, d+1); } en[i] = timer; timer++; if (d % 2 == 1) { l[i] = en[i]; } } vector<int> label(int n, int k, vector<int> u, vector<int> v) { vector<int> labels(n); timer = 0; for (int i = 0; i <= n; i++) { adj[i].clear(); en[i] = 0; } int leaf = 0; for (int i = 0; i < n-1; i++) { adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } for (int i = 0; i < n; i++) { sort(adj[i].begin(), adj[i].end()); if (adj[i].size() == 1) { leaf = i; } } dfs(leaf, -1, 0); vector<int> ind; for (int i = 0; i < n; i++) { ind.push_back(l[i]); } sort(ind.begin(), ind.end()); for (int i = 0; i < n; i++) { labels[i] = lower_bound(ind.begin(), ind.end(), l[i]) - ind.begin(); } return labels; } int find_next_station(int s, int t, vector<int> c) { int ins = -1, outs = -1; if (c.size() == 1) { return c.back(); } if (s == t) { return s; } for (int i : c) { if (i == t) { return t; } } if (s == 0) { vector<int> in(c.size()), out(c.size()); ins = s; outs = c.back()+1; for (int i = 0; i < c.size(); i++) { out[i] = c[i]; if (i == 0) { in[i] = ins+1; } else { in[i] = out[i-1]+1; } } for (int i = 0; i < c.size(); i++) { if (in[i] < t && t < out[i]) { return c[i]; } } return c.back(); } else { int inp = -1, outp = -1; vector<int> in(c.size()-1), out(c.size()-1); if (s < c.front()) { inp = s-1; outp = c.back(); c.pop_back(); ins = s; outs = c.back()+1; for (int i = 0; i < c.size(); i++) { out[i] = c[i]; if (i == 0) { in[i] = ins; } else { in[i] = out[i-1]; } } for (int i = 0; i < c.size(); i++) { if (in[i] < t && t < out[i]) { return c[i]; } } return outp; } else { inp = c.front(); outp = s+1; c.erase(c.begin()); ins = c.front()-1; outs = s; for (int i = c.size()-1; i >= 0; i--) { in[i] = c[i]; if (i == c.size()-1) { out[i] = outs; } else { out[i] = in[i+1]; } } for (int i = 0; i < c.size(); i++) { if (in[i] < t && t < out[i]) { return c[i]; } } return inp; } } }

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = 0; i < c.size(); i++) {
      |                         ~~^~~~~~~~~~
stations.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0; i < c.size(); i++) {
      |                         ~~^~~~~~~~~~
stations.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for (int i = 0; i < c.size(); i++) {
      |                             ~~^~~~~~~~~~
stations.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for (int i = 0; i < c.size(); i++) {
      |                             ~~^~~~~~~~~~
stations.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 if (i == c.size()-1) {
      |                     ~~^~~~~~~~~~~~~
stations.cpp:121:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for (int i = 0; i < c.size(); 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...