oj.uz

Submission #308613

# Submission time Handle Problem Language Result Execution time Memory
308613 2020-10-01T15:06:32 Z lordlorinc Stations (IOI20_stations) C++17
10 / 100
 1053 ms 1016 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);
	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:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = 0; i < u.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < c.size(); i++){
      |                     ~~^~~~~~~~~~
stations.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < c.size(); i++) {
      |                     ~~^~~~~~~~~~
stations.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < c.size(); i++){
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 6 ms 468 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=1165153
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 780 KB Output is correct
2 Correct 766 ms 668 KB Output is correct
3 Correct 706 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 681 ms 880 KB Output is correct
8 Correct 1041 ms 652 KB Output is correct
9 Correct 944 ms 640 KB Output is correct
10 Correct 765 ms 640 KB Output is correct
11 Correct 6 ms 668 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 561 ms 640 KB Output is correct
17 Correct 686 ms 896 KB Output is correct
18 Correct 553 ms 640 KB Output is correct
19 Correct 574 ms 652 KB Output is correct
20 Correct 531 ms 640 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 646 ms 1016 KB Wrong query response.
2 Halted 0 ms 0 KB -