oj.uz

Submission #730093

# Submission time Handle Problem Language Result Execution time Memory
730093 2023-04-25T08:54:03 Z danikoynov Stations (IOI20_stations) C++14
100 / 100
 1012 ms 892 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
vector < int > g[maxn], order, my_labels;
int in[maxn], out[maxn], timer, par[maxn], depth[maxn];
void dfs(int v, int p)
{
    if (depth[v] % 2 == 0)
    in[v] = timer ++;
    par[v] = p;
    order.push_back(v);
    for (int u : g[v])
    {

        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
    if (depth[v] % 2 == 1)
    out[v] = timer ++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    for (int i = 0; i < n; i ++)
    {
        g[i].clear();
    }
    timer = 0;
    order.clear();
    my_labels.clear();
    for (int i = 0; i < v.size(); i ++)
    {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    my_labels.resize(n);
    dfs(0, 0);
    for (int i = 0; i < n; i ++)
    {
        if (depth[i] % 2 == 0)
        my_labels[i] = in[i];
        else
            my_labels[i] = out[i];
    }


    return my_labels;
}

int used[maxn];
int find_next_station(int s, int t, vector<int> c)
{
    ///return 0;
    sort(c.begin(), c.end());
    if (c.size() == 1)
        return c[0];
    int m = c.size();
    if (s < c[0])
    {
        int tin = s;
        int tout = c[m - 2] + 1;
        if (t < tin || t > tout)
        return c[m - 1];
        int pt = 0;
        while(c[pt] < t)
            pt ++;
        return c[pt];
    }
    else
    {
        int tin = c[1] - 1;
        int tout = s;
        if (t < tin || t > tout)
        return c[0];
        int pt = c.size() - 1;
        while(c[pt] > t)
            pt --;
        return c[pt];
    }


}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 696 KB Output is correct
2 Correct 512 ms 788 KB Output is correct
3 Correct 938 ms 544 KB Output is correct
4 Correct 580 ms 536 KB Output is correct
5 Correct 592 ms 532 KB Output is correct
6 Correct 440 ms 532 KB Output is correct
7 Correct 528 ms 516 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 4 ms 556 KB Output is correct
10 Correct 2 ms 624 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 536 KB Output is correct
2 Correct 553 ms 544 KB Output is correct
3 Correct 926 ms 520 KB Output is correct
4 Correct 658 ms 484 KB Output is correct
5 Correct 584 ms 528 KB Output is correct
6 Correct 413 ms 536 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 816 KB Output is correct
2 Correct 342 ms 660 KB Output is correct
3 Correct 919 ms 556 KB Output is correct
4 Correct 741 ms 544 KB Output is correct
5 Correct 586 ms 536 KB Output is correct
6 Correct 417 ms 704 KB Output is correct
7 Correct 408 ms 548 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 0 ms 620 KB Output is correct
11 Correct 632 ms 552 KB Output is correct
12 Correct 336 ms 788 KB Output is correct
13 Correct 401 ms 796 KB Output is correct
14 Correct 485 ms 528 KB Output is correct
15 Correct 59 ms 548 KB Output is correct
16 Correct 56 ms 572 KB Output is correct
17 Correct 113 ms 544 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1012 ms 524 KB Output is correct
2 Correct 679 ms 520 KB Output is correct
3 Correct 629 ms 544 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 6 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 622 ms 528 KB Output is correct
8 Correct 857 ms 544 KB Output is correct
9 Correct 758 ms 548 KB Output is correct
10 Correct 621 ms 544 KB Output is correct
11 Correct 5 ms 628 KB Output is correct
12 Correct 5 ms 708 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 3 ms 628 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 508 ms 532 KB Output is correct
17 Correct 484 ms 544 KB Output is correct
18 Correct 501 ms 532 KB Output is correct
19 Correct 497 ms 536 KB Output is correct
20 Correct 542 ms 548 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 664 KB Output is correct
2 Correct 421 ms 676 KB Output is correct
3 Correct 782 ms 524 KB Output is correct
4 Correct 695 ms 548 KB Output is correct
5 Correct 632 ms 532 KB Output is correct
6 Correct 445 ms 656 KB Output is correct
7 Correct 457 ms 544 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 6 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 482 ms 520 KB Output is correct
12 Correct 558 ms 548 KB Output is correct
13 Correct 948 ms 520 KB Output is correct
14 Correct 638 ms 612 KB Output is correct
15 Correct 579 ms 544 KB Output is correct
16 Correct 458 ms 532 KB Output is correct
17 Correct 603 ms 532 KB Output is correct
18 Correct 450 ms 656 KB Output is correct
19 Correct 473 ms 764 KB Output is correct
20 Correct 443 ms 544 KB Output is correct
21 Correct 65 ms 544 KB Output is correct
22 Correct 69 ms 544 KB Output is correct
23 Correct 115 ms 672 KB Output is correct
24 Correct 4 ms 624 KB Output is correct
25 Correct 3 ms 628 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 620 KB Output is correct
28 Correct 2 ms 612 KB Output is correct
29 Correct 558 ms 528 KB Output is correct
30 Correct 486 ms 548 KB Output is correct
31 Correct 590 ms 532 KB Output is correct
32 Correct 587 ms 532 KB Output is correct
33 Correct 472 ms 556 KB Output is correct
34 Correct 287 ms 664 KB Output is correct
35 Correct 416 ms 784 KB Output is correct
36 Correct 410 ms 536 KB Output is correct
37 Correct 441 ms 732 KB Output is correct
38 Correct 442 ms 660 KB Output is correct
39 Correct 439 ms 772 KB Output is correct
40 Correct 419 ms 892 KB Output is correct
41 Correct 467 ms 648 KB Output is correct
42 Correct 54 ms 548 KB Output is correct
43 Correct 78 ms 532 KB Output is correct
44 Correct 121 ms 660 KB Output is correct
45 Correct 142 ms 560 KB Output is correct
46 Correct 285 ms 544 KB Output is correct
47 Correct 291 ms 544 KB Output is correct
48 Correct 62 ms 696 KB Output is correct
49 Correct 46 ms 880 KB Output is correct