Submission #305073

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305073	2020-09-22T14:08:26 Z	Haunted_Cpp	Stations (IOI20_stations)	C++17	52.3205 / 100	1178 ms	1024 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e3 + 5;

vector<vector<int>> g(MAX_N);
int Time = -1, in[MAX_N], out[MAX_N];

void dfs(int node, int p) {
  in[node] = ++Time;
  for (auto to : g[node]) {
    if (to != p) {
      dfs(to, node);
    }
  }
  out[node] = Time;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  Time = -1;
  g.clear(); g.resize(MAX_N);
	vector<int> labels(n);
  for (int i = 0; i < n - 1; i++) {
    g[u[i]].emplace_back(v[i]);
    g[v[i]].emplace_back(u[i]);
  }
  dfs(0, -1);
  for (int i = 0; i < n; i++) {
    labels[i] = in[i] * 1000 + out[i];
  }
  return labels;
}

pair<int, int> extract(int mask) {
  int out_time = mask % 1000;
  mask /= 1000;
  return make_pair(mask, out_time);
}

bool is_sub(int s, int t) {
  pair<int, int> a= extract(s);
  pair<int, int> b= extract(t);
  return (a.first <= b.first && a.second >= b.second);
}

int find_next_station(int s, int t, vector<int> c) {
  if (is_sub(s, t)) {
    for (auto mask : c) {
      if (is_sub(s, mask) && is_sub(mask, t)) {
        return mask;
      }
    }
    assert(false);
  }
  if (is_sub(t, s)) {
    for (auto mask : c) {
      if (is_sub(t, mask) && is_sub(mask, s)) {
        return mask;
      }
    }
    assert(false);
  }
  for (auto mask : c) {
    if (is_sub(mask, s)) {
      return mask;
    }
  }
  assert(false);
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	384 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	392 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	613 ms	1024 KB	Output is correct
2	Correct	555 ms	768 KB	Output is correct
3	Correct	1016 ms	968 KB	Output is correct
4	Correct	890 ms	768 KB	Output is correct
5	Correct	619 ms	768 KB	Output is correct
6	Correct	530 ms	800 KB	Output is correct
7	Correct	541 ms	896 KB	Output is correct
8	Correct	3 ms	776 KB	Output is correct
9	Correct	7 ms	768 KB	Output is correct
10	Correct	2 ms	768 KB	Output is correct
11	Correct	769 ms	1024 KB	Output is correct
12	Correct	615 ms	816 KB	Output is correct
13	Correct	556 ms	876 KB	Output is correct
14	Correct	509 ms	768 KB	Output is correct
15	Correct	61 ms	768 KB	Output is correct
16	Correct	83 ms	800 KB	Output is correct
17	Correct	136 ms	776 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1178 ms	900 KB	Output is correct
2	Correct	805 ms	768 KB	Output is correct
3	Correct	742 ms	776 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	2 ms	768 KB	Output is correct
7	Correct	644 ms	768 KB	Output is correct
8	Correct	893 ms	896 KB	Output is correct
9	Correct	938 ms	848 KB	Output is correct
10	Correct	717 ms	768 KB	Output is correct
11	Correct	7 ms	768 KB	Output is correct
12	Correct	4 ms	768 KB	Output is correct
13	Correct	8 ms	768 KB	Output is correct
14	Correct	4 ms	896 KB	Output is correct
15	Correct	1 ms	768 KB	Output is correct
16	Correct	678 ms	800 KB	Output is correct
17	Correct	665 ms	768 KB	Output is correct
18	Correct	610 ms	768 KB	Output is correct
19	Correct	589 ms	768 KB	Output is correct
20	Correct	623 ms	768 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	615 ms	784 KB	Partially correct
2	Partially correct	645 ms	768 KB	Partially correct
3	Partially correct	1174 ms	768 KB	Partially correct
4	Partially correct	876 ms	784 KB	Partially correct
5	Partially correct	736 ms	768 KB	Partially correct
6	Partially correct	597 ms	1016 KB	Partially correct
7	Partially correct	606 ms	792 KB	Partially correct
8	Partially correct	3 ms	768 KB	Partially correct
9	Partially correct	5 ms	776 KB	Partially correct
10	Partially correct	2 ms	872 KB	Partially correct
11	Partially correct	514 ms	768 KB	Partially correct
12	Partially correct	592 ms	896 KB	Partially correct
13	Partially correct	1083 ms	800 KB	Partially correct
14	Partially correct	818 ms	800 KB	Partially correct
15	Partially correct	690 ms	896 KB	Partially correct
16	Partially correct	633 ms	896 KB	Partially correct
17	Partially correct	703 ms	768 KB	Partially correct
18	Partially correct	609 ms	888 KB	Partially correct
19	Partially correct	659 ms	768 KB	Partially correct
20	Partially correct	519 ms	952 KB	Partially correct
21	Partially correct	90 ms	832 KB	Partially correct
22	Partially correct	93 ms	840 KB	Partially correct
23	Partially correct	122 ms	768 KB	Partially correct
24	Partially correct	5 ms	800 KB	Partially correct
25	Partially correct	5 ms	768 KB	Partially correct
26	Partially correct	6 ms	868 KB	Partially correct
27	Partially correct	6 ms	768 KB	Partially correct
28	Partially correct	2 ms	768 KB	Partially correct
29	Partially correct	578 ms	800 KB	Partially correct
30	Partially correct	670 ms	792 KB	Partially correct
31	Partially correct	630 ms	892 KB	Partially correct
32	Partially correct	560 ms	800 KB	Partially correct
33	Partially correct	751 ms	832 KB	Partially correct
34	Partially correct	350 ms	1024 KB	Partially correct
35	Partially correct	584 ms	884 KB	Partially correct
36	Partially correct	468 ms	880 KB	Partially correct
37	Partially correct	595 ms	968 KB	Partially correct
38	Partially correct	534 ms	800 KB	Partially correct
39	Partially correct	618 ms	876 KB	Partially correct
40	Partially correct	631 ms	988 KB	Partially correct
41	Partially correct	560 ms	920 KB	Partially correct
42	Partially correct	72 ms	896 KB	Partially correct
43	Partially correct	157 ms	768 KB	Partially correct
44	Partially correct	182 ms	800 KB	Partially correct
45	Partially correct	193 ms	992 KB	Partially correct
46	Partially correct	371 ms	904 KB	Partially correct
47	Partially correct	320 ms	912 KB	Partially correct
48	Partially correct	93 ms	832 KB	Partially correct
49	Partially correct	81 ms	768 KB	Partially correct