oj.uz

Submission #605201

# Submission time Handle Problem Language Result Execution time Memory
605201 2022-07-25T13:50:15 Z lcj Stations (IOI20_stations) C++17
52.3205 / 100
 975 ms 732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#include "stations.h"
#define fi first
#define se second


void dfs(int cn, vector<int> &tin, vector<int> &tout, vector<vector<int>> &neighbours, int &cnt) {
    cnt++;
    tin[cn] = cnt;
    for (int nn : neighbours[cn]) {
        if (tin[nn] != -1) continue;
        dfs(nn, tin, tout, neighbours, cnt);
    }
    tout[cn] = cnt;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n, -1);
    vector<vector<int>> adj(n);
    for (int i = 0; i < u.size(); i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    vector<int> tin(n, -1);
    vector<int> tout(n, -1);
    int cnt = -1;
    dfs(0, tin, tout, adj, cnt);
    if (cnt != n-1) {
        return {};
    }
    for (int i = 0; i < n; i++)
    {
        labels[i] = tin[i]*1000+tout[i];
    }
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    pii m = {s / 1000, s % 1000};
    pii o = {t / 1000, t % 1000};
    vector<pii> vals;
    for (int i : c) {
        vals.push_back({i / 1000, i % 1000});
    }
    sort(vals.begin(), vals.end());
    for (int i = 1; i < vals.size(); i++)
    {
        if (vals[i].fi <= o.fi && o.fi <= vals[i].se) {
            return vals[i].fi*1000+vals[i].se;
        }
    }
    return vals[0].fi*1000+vals[0].se;
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     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<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 1; i < vals.size(); i++)
      |                     ~~^~~~~~~~~~~~~
stations.cpp:47:9: warning: variable 'm' set but not used [-Wunused-but-set-variable]
   47 |     pii m = {s / 1000, s % 1000};
      |         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 420 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 6 ms 296 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 672 ms 640 KB Output is correct
2 Correct 552 ms 636 KB Output is correct
3 Correct 975 ms 492 KB Output is correct
4 Correct 653 ms 504 KB Output is correct
5 Correct 597 ms 492 KB Output is correct
6 Correct 467 ms 544 KB Output is correct
7 Correct 443 ms 544 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 589 ms 416 KB Output is correct
12 Correct 466 ms 636 KB Output is correct
13 Correct 427 ms 620 KB Output is correct
14 Correct 482 ms 504 KB Output is correct
15 Correct 48 ms 456 KB Output is correct
16 Correct 61 ms 544 KB Output is correct
17 Correct 99 ms 536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 512 KB Output is correct
2 Correct 565 ms 416 KB Output is correct
3 Correct 481 ms 416 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 483 ms 508 KB Output is correct
8 Correct 866 ms 504 KB Output is correct
9 Correct 618 ms 416 KB Output is correct
10 Correct 482 ms 420 KB Output is correct
11 Correct 5 ms 496 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 443 ms 508 KB Output is correct
17 Correct 363 ms 420 KB Output is correct
18 Correct 536 ms 504 KB Output is correct
19 Correct 440 ms 504 KB Output is correct
20 Correct 491 ms 508 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 525 ms 544 KB Partially correct
2 Partially correct 441 ms 636 KB Partially correct
3 Partially correct 696 ms 416 KB Partially correct
4 Partially correct 656 ms 504 KB Partially correct
5 Partially correct 532 ms 504 KB Partially correct
6 Partially correct 482 ms 544 KB Partially correct
7 Partially correct 490 ms 548 KB Partially correct
8 Partially correct 2 ms 492 KB Partially correct
9 Partially correct 3 ms 492 KB Partially correct
10 Partially correct 1 ms 492 KB Partially correct
11 Partially correct 450 ms 504 KB Partially correct
12 Partially correct 495 ms 548 KB Partially correct
13 Partially correct 808 ms 508 KB Partially correct
14 Partially correct 615 ms 420 KB Partially correct
15 Partially correct 523 ms 504 KB Partially correct
16 Partially correct 452 ms 544 KB Partially correct
17 Partially correct 597 ms 416 KB Partially correct
18 Partially correct 461 ms 632 KB Partially correct
19 Partially correct 441 ms 720 KB Partially correct
20 Partially correct 463 ms 544 KB Partially correct
21 Partially correct 60 ms 420 KB Partially correct
22 Partially correct 66 ms 544 KB Partially correct
23 Partially correct 105 ms 544 KB Partially correct
24 Partially correct 5 ms 492 KB Partially correct
25 Partially correct 4 ms 500 KB Partially correct
26 Partially correct 4 ms 500 KB Partially correct
27 Partially correct 2 ms 492 KB Partially correct
28 Partially correct 1 ms 488 KB Partially correct
29 Partially correct 454 ms 500 KB Partially correct
30 Partially correct 518 ms 416 KB Partially correct
31 Partially correct 410 ms 512 KB Partially correct
32 Partially correct 553 ms 504 KB Partially correct
33 Partially correct 571 ms 504 KB Partially correct
34 Partially correct 368 ms 656 KB Partially correct
35 Partially correct 367 ms 732 KB Partially correct
36 Partially correct 439 ms 696 KB Partially correct
37 Partially correct 457 ms 684 KB Partially correct
38 Partially correct 449 ms 596 KB Partially correct
39 Partially correct 455 ms 596 KB Partially correct
40 Partially correct 446 ms 716 KB Partially correct
41 Partially correct 474 ms 696 KB Partially correct
42 Partially correct 55 ms 548 KB Partially correct
43 Partially correct 103 ms 504 KB Partially correct
44 Partially correct 143 ms 544 KB Partially correct
45 Partially correct 151 ms 504 KB Partially correct
46 Partially correct 285 ms 544 KB Partially correct
47 Partially correct 330 ms 500 KB Partially correct
48 Partially correct 57 ms 548 KB Partially correct
49 Partially correct 49 ms 632 KB Partially correct