oj.uz

Submission #305319

# Submission time Handle Problem Language Result Execution time Memory
305319 2020-09-22T23:47:39 Z Fdg Stations (IOI20_stations) C++14
100 / 100
 1117 ms 1136 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <memory.h>

using namespace std;

vector<int> g[1002];
vector<int> color;
bool used[1002];
int ptr;

void dfs(int v, bool markFirst) {
  used[v] = true;
  if (markFirst) color[v] = ptr++;
  for (int x : g[v])
   if (!used[x]) dfs(x, !markFirst);
  if (!markFirst) color[v] = ptr++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  for (int i = 0; i < n; ++i) g[i].clear();
  for (int i = 0; i < u.size(); ++i) {
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
  }

  ptr = 0;
  color.resize(n, -1);
  memset(used, false, sizeof(used));
  dfs(0, true);
  return color;
}

int find_next_station(int s, int t, vector<int> st) {
  sort(st.begin(), st.end());
  if (s < st[0]) {
    if (t < s) return st.back();
    for (int x : st)
      if (t <= x) return x;
    return st.back();
  } else {
    if (t > s) return st[0];
    for (int i = st.size() - 1; i >= 0; --i)
      if (st[i] <= t) return st[i];
    return st[0];
  }
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int i = 0; i < u.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 1012 KB Output is correct
2 Correct 477 ms 1024 KB Output is correct
3 Correct 870 ms 876 KB Output is correct
4 Correct 688 ms 1136 KB Output is correct
5 Correct 659 ms 880 KB Output is correct
6 Correct 467 ms 992 KB Output is correct
7 Correct 450 ms 792 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 5 ms 872 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 768 KB Output is correct
2 Correct 647 ms 820 KB Output is correct
3 Correct 1117 ms 1032 KB Output is correct
4 Correct 909 ms 876 KB Output is correct
5 Correct 663 ms 768 KB Output is correct
6 Correct 661 ms 824 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 1012 KB Output is correct
2 Correct 667 ms 768 KB Output is correct
3 Correct 922 ms 1032 KB Output is correct
4 Correct 646 ms 884 KB Output is correct
5 Correct 701 ms 876 KB Output is correct
6 Correct 642 ms 772 KB Output is correct
7 Correct 523 ms 788 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 781 ms 876 KB Output is correct
12 Correct 594 ms 892 KB Output is correct
13 Correct 491 ms 900 KB Output is correct
14 Correct 543 ms 824 KB Output is correct
15 Correct 71 ms 880 KB Output is correct
16 Correct 72 ms 844 KB Output is correct
17 Correct 112 ms 1024 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 1008 KB Output is correct
2 Correct 772 ms 880 KB Output is correct
3 Correct 673 ms 876 KB Output is correct
4 Correct 2 ms 872 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 636 ms 768 KB Output is correct
8 Correct 883 ms 768 KB Output is correct
9 Correct 756 ms 1004 KB Output is correct
10 Correct 672 ms 1032 KB Output is correct
11 Correct 7 ms 880 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 604 ms 900 KB Output is correct
17 Correct 589 ms 1004 KB Output is correct
18 Correct 512 ms 768 KB Output is correct
19 Correct 591 ms 876 KB Output is correct
20 Correct 544 ms 880 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 1024 KB Output is correct
2 Correct 523 ms 768 KB Output is correct
3 Correct 1025 ms 768 KB Output is correct
4 Correct 689 ms 768 KB Output is correct
5 Correct 581 ms 876 KB Output is correct
6 Correct 449 ms 776 KB Output is correct
7 Correct 447 ms 1036 KB Output is correct
8 Correct 3 ms 884 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 477 ms 808 KB Output is correct
12 Correct 552 ms 832 KB Output is correct
13 Correct 865 ms 872 KB Output is correct
14 Correct 687 ms 872 KB Output is correct
15 Correct 710 ms 1008 KB Output is correct
16 Correct 526 ms 828 KB Output is correct
17 Correct 669 ms 768 KB Output is correct
18 Correct 482 ms 912 KB Output is correct
19 Correct 523 ms 892 KB Output is correct
20 Correct 586 ms 768 KB Output is correct
21 Correct 60 ms 768 KB Output is correct
22 Correct 68 ms 844 KB Output is correct
23 Correct 99 ms 768 KB Output is correct
24 Correct 7 ms 880 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 6 ms 884 KB Output is correct
27 Correct 4 ms 888 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 537 ms 1024 KB Output is correct
30 Correct 567 ms 876 KB Output is correct
31 Correct 500 ms 1024 KB Output is correct
32 Correct 600 ms 768 KB Output is correct
33 Correct 559 ms 876 KB Output is correct
34 Correct 343 ms 1008 KB Output is correct
35 Correct 478 ms 1024 KB Output is correct
36 Correct 490 ms 772 KB Output is correct
37 Correct 479 ms 768 KB Output is correct
38 Correct 516 ms 780 KB Output is correct
39 Correct 512 ms 768 KB Output is correct
40 Correct 581 ms 1024 KB Output is correct
41 Correct 571 ms 888 KB Output is correct
42 Correct 65 ms 768 KB Output is correct
43 Correct 103 ms 808 KB Output is correct
44 Correct 131 ms 796 KB Output is correct
45 Correct 154 ms 792 KB Output is correct
46 Correct 310 ms 768 KB Output is correct
47 Correct 311 ms 768 KB Output is correct
48 Correct 72 ms 768 KB Output is correct
49 Correct 64 ms 1028 KB Output is correct