oj.uz

Submission #319757

# Submission time Handle Problem Language Result Execution time Memory
319757 2020-11-06T11:24:05 Z spatarel Stations (IOI20_stations) C++17
16 / 100
 950 ms 1044 KB 
#include "stations.h"
#include <algorithm>
#include <stdio.h>
#include <vector>

const int MAX_N = 1000;

bool visited[MAX_N];
std::vector<int> neighbours[MAX_N];
int counter;

void visit(std::vector<int> &labels, int u) {
  labels[u] = counter;
  //printf("%d->%d\n", u, counter);
  counter++;
}

void dfs(std::vector<int> &labels, int u, bool parity = false) {
  //printf("dfs: %d %d\n", u, parity);
  visited[u] = true;
  if (parity) {
    visit(labels, u);
  }
  for (int v : neighbours[u]) {
    if (!visited[v]) {
      dfs(labels, v, !parity);
    }
  }
  if (!parity) {
    visit(labels, u);
  }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  std::vector<int> labels(n);
  for (int i = 0; i < n - 1; i++) {
    neighbours[u[i]].push_back(v[i]);
    neighbours[v[i]].push_back(u[i]);
  }
  counter = 0;
  for (int i = 0; i < n; i++) {
    visited[i] = false;
  }
  dfs(labels, 0);
  for (int i = 0; i < n; i++) {
    neighbours[i].clear();
  }
  return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
  if (c.size() == 1) {
    return c[0];
  }
  int answer;
  std::sort(c.begin(), c.end());
  /*
  for (int n : c) {
    printf("%d ", n);
  }
  printf("\n");//*/
  if (s < c[0]) {
    int p = c.back();
    int l = s;
    int r = c.end()[-2];
    if (l <= t && t <= r) {
      int i = c.size() - 2;
      while (i >= 0 && t <= c[i]) {
        i--;
      }
      answer = c[i + 1];
    } else {
      answer = p;
    }
  } else {
    int p = c[0];
    int l = c[1];
    int r = s;
    //printf("%d %d\n", l, r);
    if (l <= t && t <= r) {
      int i = 1;
      while (i < (int)c.size() && c[i] <= t) {
        i++;
      }
      answer = c[i - 1];
    } else {
      answer = p;
    }
  }
  //printf("%d->%d (%d)\n", s, t, answer);
  return answer;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 0 KB Execution failed because of sandbox error
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 0 KB Execution failed because of sandbox error
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 1044 KB Output is correct
2 Correct 475 ms 864 KB Output is correct
3 Correct 887 ms 856 KB Output is correct
4 Correct 685 ms 756 KB Output is correct
5 Correct 603 ms 856 KB Output is correct
6 Correct 455 ms 1040 KB Output is correct
7 Correct 475 ms 884 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 2 ms 864 KB Output is correct
11 Correct 617 ms 864 KB Output is correct
12 Correct 454 ms 992 KB Output is correct
13 Correct 484 ms 984 KB Output is correct
14 Correct 453 ms 756 KB Output is correct
15 Correct 58 ms 864 KB Output is correct
16 Correct 68 ms 864 KB Output is correct
17 Correct 113 ms 916 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 840 KB Output is correct
2 Correct 669 ms 852 KB Output is correct
3 Correct 602 ms 756 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 2 ms 1012 KB Output is correct
7 Correct 563 ms 856 KB Output is correct
8 Correct 950 ms 864 KB Output is correct
9 Failed 0 ms 0 KB Execution failed because of sandbox error
10 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 884 KB Output is correct
2 Correct 452 ms 1012 KB Output is correct
3 Correct 905 ms 960 KB Output is correct
4 Failed 0 ms 0 KB Execution failed because of sandbox error
5 Halted 0 ms 0 KB -