# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
931496 | 2024-02-21T23:58:57 Z | beaboss | Stations (IOI20_stations) | C++14 | 543 ms | 940 KB |
#include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<int> vi; #define FOR(i, a, b) for (int i = (a); i<b; i++) bool ckmin(int& a, int b){ return b < a ? a = b, true : false; } bool ckmax(int& a, int b){ return b > a ? a = b, true : false; } const int N = 1010; vi adj[N]; vi out; int cnt = 0; void dfs(int cur, int d = 0, int p = -1) { if (d % 2 == 0) out[cur] = cnt; cnt++; for (auto val: adj[cur]) if (val != p) dfs(val, d + 1, cur); if (d % 2 == 1) out[cur] = cnt; cnt++; } vi label(int n, int k, vi u, vi v) { cnt = 0; out.resize(0); FOR(i, 0, N) adj[i].clear(); FOR(i, 0, u.size()) { adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); } out.resize(n); dfs(0); vi other = out; sort(other.begin(), other.end()); FOR(i, 0, out.size()) out[i] = lower_bound(other.begin(), other.end(), out[i]) - other.begin(); return out; } int find_next_station(int s, int t, vi c) { assert(s <= c[0] || s >= c[c.size() - 1]); if (s < c[0]) { // everything is end int p = c[c.size() - 1]; int st = s; // inclusive boud int en = s; // inclusive if (c.size() >= 2) en = max(en, c[c.size() - 2]-1); if (t > en || t < st) return p; return *lower_bound(c.begin(), c.begin() + c.size() - 1, t); } else { int p = c[0]; int st = s-1; // inclusive int en = s-1; // inclusive // cout << st << en << endl; if (c.size() >= 2) st = min(st, c[1]); // cout << st << en << endl; if (t > en || t < st) return p; // cout << t << endl; return *prev(lower_bound(c.begin() + 1, c.end(), t), 1); } } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // vi res = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4}); // for (auto val: res) cout << val << endl; // // cout << find_next_station(2, 0, {4, 6, 8}) << endl; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 365 ms | 932 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 281 ms | 872 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 352 ms | 940 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 543 ms | 684 KB | Output is correct |
2 | Incorrect | 453 ms | 684 KB | Wrong query response. |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 355 ms | 936 KB | Wrong query response. |
2 | Halted | 0 ms | 0 KB | - |