oj.uz

Submission #308621

# Submission time Handle Problem Language Result Execution time Memory
308621 2020-10-01T15:09:44 Z lordlorinc Stations (IOI20_stations) C++17
31.0422 / 100
 1190 ms 1268 KB 
#include "stations.h"
#include <vector>

using namespace std;

vector<vector<int> > sor;
vector<bool> volt;
vector<int> eleres, tavozas;
int time = -1;

void bejaras (int hely){
    time++;
    eleres[hely] = time;
    volt[hely] = true;
    for (int x : sor[hely]){
        if (volt[x] == false){
            bejaras(x);
        }
    }
    time++;
    tavozas[hely] = time;
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	sor.assign(n, vector<int>(0));
	volt.assign(n, false);
	eleres.assign(n, 0);
	tavozas.assign(n, 0);
	time = -1;
	for (int i = 0; i < u.size(); i++){
        sor[u[i]].push_back(v[i]);
        sor[v[i]].push_back(u[i]);
	}

	bejaras(0);

	vector<int> labels(n);

	for (int i = 0; i < n; i++) labels[i] = eleres[i] * 2000 + tavozas[i];

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

    pair<int, int> hely, cel;
    hely.first = s / 2000;
    hely.second = s % 2000;
    cel.first = t / 2000;
    cel.second = t % 2000;

    vector<pair<int, int> > szomszedok(c.size());

    for (int i = 0; i < c.size(); i++){
        szomszedok[i].first = c[i] / 2000;
        szomszedok[i].second = c[i] % 2000;
    }

    int szuloindex = -1;
    for (int i = 0; i < c.size(); i++) {
        if (szomszedok[i].first < hely.first) szuloindex = i;
    }

    for (int i = 0; i < c.size(); i++){
        if (i != szuloindex){
            if (szomszedok[i].first <= cel.first && szomszedok[i].second >= cel.second){
                return c[i];
            }
        }
    }



	return c[szuloindex];
}

Compilation message

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

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=14014
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=3, label=1157149
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 640 KB Output is correct
2 Correct 702 ms 640 KB Output is correct
3 Correct 724 ms 736 KB Output is correct
4 Correct 3 ms 652 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 1 ms 664 KB Output is correct
7 Correct 759 ms 768 KB Output is correct
8 Correct 1190 ms 640 KB Output is correct
9 Correct 731 ms 736 KB Output is correct
10 Correct 799 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 6 ms 660 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 5 ms 656 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 733 ms 740 KB Output is correct
17 Correct 680 ms 640 KB Output is correct
18 Correct 571 ms 656 KB Output is correct
19 Correct 557 ms 652 KB Output is correct
20 Correct 707 ms 640 KB Output is correct

Subtask #5
21.0422 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 567 ms 1024 KB Partially correct
2 Partially correct 600 ms 760 KB Partially correct
3 Partially correct 1061 ms 640 KB Partially correct
4 Partially correct 768 ms 640 KB Partially correct
5 Partially correct 759 ms 860 KB Partially correct
6 Partially correct 501 ms 784 KB Partially correct
7 Partially correct 594 ms 808 KB Partially correct
8 Partially correct 2 ms 660 KB Partially correct
9 Partially correct 3 ms 640 KB Partially correct
10 Partially correct 2 ms 896 KB Partially correct
11 Partially correct 488 ms 1268 KB Partially correct
12 Partially correct 571 ms 832 KB Partially correct
13 Partially correct 902 ms 656 KB Partially correct
14 Partially correct 698 ms 640 KB Partially correct
15 Partially correct 607 ms 664 KB Partially correct
16 Partially correct 463 ms 832 KB Partially correct
17 Partially correct 628 ms 664 KB Partially correct
18 Partially correct 478 ms 920 KB Partially correct
19 Partially correct 511 ms 768 KB Partially correct
20 Partially correct 506 ms 828 KB Partially correct
21 Partially correct 66 ms 640 KB Partially correct
22 Partially correct 83 ms 1024 KB Partially correct
23 Partially correct 114 ms 768 KB Partially correct
24 Partially correct 7 ms 640 KB Partially correct
25 Partially correct 5 ms 640 KB Partially correct
26 Partially correct 5 ms 812 KB Partially correct
27 Partially correct 4 ms 640 KB Partially correct
28 Partially correct 2 ms 640 KB Partially correct
29 Partially correct 541 ms 668 KB Partially correct
30 Partially correct 611 ms 836 KB Partially correct
31 Partially correct 607 ms 656 KB Partially correct
32 Partially correct 653 ms 652 KB Partially correct
33 Partially correct 570 ms 656 KB Partially correct
34 Partially correct 405 ms 1024 KB Partially correct
35 Partially correct 495 ms 776 KB Partially correct
36 Partially correct 516 ms 1024 KB Partially correct
37 Partially correct 548 ms 776 KB Partially correct
38 Partially correct 494 ms 780 KB Partially correct
39 Partially correct 471 ms 788 KB Partially correct
40 Partially correct 492 ms 1248 KB Partially correct
41 Partially correct 527 ms 796 KB Partially correct
42 Partially correct 84 ms 768 KB Partially correct
43 Partially correct 110 ms 768 KB Partially correct
44 Partially correct 169 ms 808 KB Partially correct
45 Partially correct 201 ms 960 KB Partially correct
46 Partially correct 345 ms 768 KB Partially correct
47 Partially correct 325 ms 796 KB Partially correct
48 Partially correct 76 ms 768 KB Partially correct
49 Partially correct 80 ms 768 KB Partially correct