| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 317508 |
2020-10-30T00:28:55 Z |
rqi |
Stations (IOI20_stations) |
C++14 |
|
1009 ms |
1148 KB |
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define bk back()
#define mp make_pair
#define f first
#define s second
#define all(x) begin(x), end(x)
const int mx = 1005;
vi adj[mx];
int depth[mx];
pi rang[mx];
int cnt = 0;
vi labels;
void genET(int node, int prv = -1, int d = 0){
depth[node] = d;
cnt++;
rang[node].f = rang[node].s = cnt;
for(auto u: adj[node]){
if(u == prv) continue;
genET(u, node, d+1);
cnt++;
rang[node].s = cnt;
}
if(depth[node] % 2 == 0){
labels[node] = rang[node].f;
}
else labels[node] = rang[node].s;
}
vi label(int n, int k, vi u, vi v) {
for(int i = 0; i < n; i++){
adj[i].clear();
}
for(int i = 0; i < n-1; i++){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
labels = vi(n);
genET(0);
map<int, int> m;
for(auto u: labels) m[u];
cnt = 0;
for(auto &u: m){
u.s = cnt++;
}
for(auto &u: labels) u = m[u];
return labels;
}
int find_next_station(int s, int t, vi c) {
bool typ = 0;
if(c[0] < s) typ = 1;
if(typ == 0){
sort(all(c));
if(t < s) return c.bk;
for(auto u: c) if(u >= t) return u;
return c.bk;
}
else{
sort(c.rbegin(), c.rend());
if(t > s) return c.bk;
for(auto u: c) if(u <= t) return u;
return c.bk;
}
assert(0 == 1);
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
597 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
474 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
978 ms |
996 KB |
Output is correct |
| 4 |
Correct |
689 ms |
868 KB |
Output is correct |
| 5 |
Correct |
595 ms |
768 KB |
Output is correct |
| 6 |
Correct |
557 ms |
1056 KB |
Output is correct |
| 7 |
Correct |
499 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
2 ms |
768 KB |
Output is correct |
| 9 |
Correct |
5 ms |
868 KB |
Output is correct |
| 10 |
Correct |
2 ms |
872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
548 ms |
1096 KB |
Output is correct |
| 2 |
Correct |
623 ms |
768 KB |
Output is correct |
| 3 |
Correct |
839 ms |
872 KB |
Output is correct |
| 4 |
Correct |
698 ms |
768 KB |
Output is correct |
| 5 |
Correct |
723 ms |
868 KB |
Output is correct |
| 6 |
Correct |
446 ms |
772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
531 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
541 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
915 ms |
868 KB |
Output is correct |
| 4 |
Correct |
681 ms |
872 KB |
Output is correct |
| 5 |
Correct |
603 ms |
864 KB |
Output is correct |
| 6 |
Correct |
489 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
508 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
864 KB |
Output is correct |
| 9 |
Correct |
5 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| 11 |
Correct |
677 ms |
768 KB |
Output is correct |
| 12 |
Correct |
611 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
498 ms |
1068 KB |
Output is correct |
| 14 |
Correct |
508 ms |
1024 KB |
Output is correct |
| 15 |
Correct |
49 ms |
1144 KB |
Output is correct |
| 16 |
Correct |
83 ms |
804 KB |
Output is correct |
| 17 |
Correct |
118 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
872 ms |
768 KB |
Output is correct |
| 2 |
Correct |
785 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
670 ms |
872 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
4 ms |
872 KB |
Output is correct |
| 6 |
Correct |
2 ms |
876 KB |
Output is correct |
| 7 |
Correct |
695 ms |
800 KB |
Output is correct |
| 8 |
Correct |
1009 ms |
868 KB |
Output is correct |
| 9 |
Correct |
671 ms |
768 KB |
Output is correct |
| 10 |
Correct |
633 ms |
876 KB |
Output is correct |
| 11 |
Correct |
6 ms |
880 KB |
Output is correct |
| 12 |
Correct |
7 ms |
768 KB |
Output is correct |
| 13 |
Correct |
5 ms |
768 KB |
Output is correct |
| 14 |
Correct |
4 ms |
768 KB |
Output is correct |
| 15 |
Correct |
1 ms |
868 KB |
Output is correct |
| 16 |
Correct |
605 ms |
876 KB |
Output is correct |
| 17 |
Correct |
505 ms |
872 KB |
Output is correct |
| 18 |
Correct |
579 ms |
768 KB |
Output is correct |
| 19 |
Correct |
573 ms |
768 KB |
Output is correct |
| 20 |
Correct |
532 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
681 ms |
1008 KB |
Output is correct |
| 2 |
Correct |
466 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
858 ms |
768 KB |
Output is correct |
| 4 |
Correct |
648 ms |
1040 KB |
Output is correct |
| 5 |
Correct |
657 ms |
768 KB |
Output is correct |
| 6 |
Correct |
525 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
538 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
2 ms |
872 KB |
Output is correct |
| 9 |
Correct |
6 ms |
884 KB |
Output is correct |
| 10 |
Correct |
2 ms |
768 KB |
Output is correct |
| 11 |
Correct |
546 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
670 ms |
1148 KB |
Output is correct |
| 13 |
Correct |
995 ms |
868 KB |
Output is correct |
| 14 |
Correct |
772 ms |
872 KB |
Output is correct |
| 15 |
Correct |
667 ms |
776 KB |
Output is correct |
| 16 |
Correct |
479 ms |
768 KB |
Output is correct |
| 17 |
Correct |
568 ms |
768 KB |
Output is correct |
| 18 |
Correct |
580 ms |
1096 KB |
Output is correct |
| 19 |
Correct |
553 ms |
1024 KB |
Output is correct |
| 20 |
Correct |
544 ms |
1024 KB |
Output is correct |
| 21 |
Correct |
60 ms |
852 KB |
Output is correct |
| 22 |
Correct |
76 ms |
768 KB |
Output is correct |
| 23 |
Correct |
118 ms |
1024 KB |
Output is correct |
| 24 |
Correct |
6 ms |
768 KB |
Output is correct |
| 25 |
Correct |
8 ms |
768 KB |
Output is correct |
| 26 |
Correct |
4 ms |
864 KB |
Output is correct |
| 27 |
Correct |
4 ms |
768 KB |
Output is correct |
| 28 |
Correct |
2 ms |
768 KB |
Output is correct |
| 29 |
Correct |
524 ms |
1040 KB |
Output is correct |
| 30 |
Correct |
529 ms |
1024 KB |
Output is correct |
| 31 |
Correct |
623 ms |
768 KB |
Output is correct |
| 32 |
Correct |
561 ms |
768 KB |
Output is correct |
| 33 |
Correct |
514 ms |
768 KB |
Output is correct |
| 34 |
Correct |
337 ms |
1024 KB |
Output is correct |
| 35 |
Correct |
495 ms |
1024 KB |
Output is correct |
| 36 |
Correct |
530 ms |
1024 KB |
Output is correct |
| 37 |
Correct |
471 ms |
1024 KB |
Output is correct |
| 38 |
Correct |
535 ms |
1024 KB |
Output is correct |
| 39 |
Correct |
556 ms |
1024 KB |
Output is correct |
| 40 |
Correct |
552 ms |
1024 KB |
Output is correct |
| 41 |
Correct |
550 ms |
1024 KB |
Output is correct |
| 42 |
Correct |
86 ms |
784 KB |
Output is correct |
| 43 |
Correct |
118 ms |
1024 KB |
Output is correct |
| 44 |
Correct |
151 ms |
1024 KB |
Output is correct |
| 45 |
Correct |
188 ms |
1024 KB |
Output is correct |
| 46 |
Correct |
363 ms |
784 KB |
Output is correct |
| 47 |
Correct |
353 ms |
1024 KB |
Output is correct |
| 48 |
Correct |
92 ms |
1024 KB |
Output is correct |
| 49 |
Correct |
82 ms |
1088 KB |
Output is correct |
