oj.uz

답안 #432368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432368 2021-06-18T08:38:51 Z idk321 기지국 (IOI20_stations) C++17
73.3627 / 100
 975 ms 916 KB 
#include "stations.h"
#include <vector>

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

const int M = 1000000000;
const int N = 1000;
int in[N];
int out[N];
vector<int> adj[N];
vector<int> labels;

int n, k;

int timer;

int type[N];


void dfs2(int node, int par)
{
    if (par == -1)
    {
        type[node] = 0;

    } else
    {
        type[node] = !type[par];

    }


    in[node] = timer;
    timer++;

    for (int next : adj[node])
    {
        if (next == par) continue;
        dfs2(next, node);
    }

    out[node] = timer;
    timer++;
}


const int add = 2000;


std::vector<int> label(int n1, int k1, std::vector<int> u, std::vector<int> v) {
    n = n1;
    k = k1;

    labels.assign(n, 0);


    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < u.size(); i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }




    timer = 0;
    dfs2(0, -1);



    for (int i = 0; i < n; i++) {
        if (type[i] == 0) labels[i] = in[i] + add;
        else labels[i] = out[i];
    }
    return labels;
}



int find_next_station(int s, int t, std::vector<int> c) {
    if (t >= add) t -= add;
    if (s >= add)
    {
        s -= add;
        int par = -1;
        if (s != 0)
        {
            for (int next : c)
            {
                if (par < next)
                {
                    par = next;
                }
            }
        }


        if (t < s) return par;

        int take = M;
        for (int next : c)
        {
            if (next == par) continue;
            if (next < take && next >= t)
            {
                take = next;
            }

        }
        if (take == M) return par;
        return take;
    } else
    {
        int par = M;
        for (int& next : c)
        {

            next -= add;
            if (next < par) par = next;
        }


        if (t > s) return par + add;
        vector<int> children;
        for (int next : c)
        {
            if (next == par) continue;
            children.push_back(next);
        }


        if (t <= par) return par + add;

        int take = -1;
        for (int i = 0; i < children.size(); i++)
        {
            if (children[i] > t) break;
            take = i;
        }

        if (take == -1) return par + add;
        return children[take] + add;
    }






    return c[0];
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 428 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=2000
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 308 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=2000
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 588 ms 840 KB Output is correct
2 Correct 472 ms 528 KB Output is correct
3 Correct 836 ms 500 KB Output is correct
4 Correct 714 ms 516 KB Output is correct
5 Correct 649 ms 632 KB Output is correct
6 Correct 485 ms 644 KB Output is correct
7 Correct 459 ms 528 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 627 ms 548 KB Output is correct
12 Correct 526 ms 616 KB Output is correct
13 Correct 471 ms 752 KB Output is correct
14 Correct 433 ms 512 KB Output is correct
15 Correct 62 ms 576 KB Output is correct
16 Correct 68 ms 684 KB Output is correct
17 Correct 107 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 975 ms 508 KB Output is correct
2 Correct 690 ms 400 KB Output is correct
3 Correct 658 ms 584 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 9 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 682 ms 400 KB Output is correct
8 Correct 902 ms 420 KB Output is correct
9 Correct 609 ms 516 KB Output is correct
10 Correct 626 ms 512 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 559 ms 512 KB Output is correct
17 Correct 511 ms 516 KB Output is correct
18 Correct 549 ms 512 KB Output is correct
19 Correct 522 ms 644 KB Output is correct
20 Correct 568 ms 616 KB Output is correct

Subtask #5
47.3627 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 496 ms 624 KB Partially correct
2 Partially correct 474 ms 508 KB Partially correct
3 Partially correct 859 ms 728 KB Partially correct
4 Partially correct 704 ms 528 KB Partially correct
5 Partially correct 640 ms 528 KB Partially correct
6 Partially correct 462 ms 628 KB Partially correct
7 Partially correct 449 ms 648 KB Partially correct
8 Partially correct 3 ms 596 KB Partially correct
9 Partially correct 6 ms 596 KB Partially correct
10 Partially correct 2 ms 596 KB Partially correct
11 Partially correct 513 ms 528 KB Partially correct
12 Partially correct 583 ms 640 KB Partially correct
13 Partially correct 852 ms 636 KB Partially correct
14 Partially correct 697 ms 528 KB Partially correct
15 Partially correct 610 ms 512 KB Partially correct
16 Partially correct 518 ms 528 KB Partially correct
17 Partially correct 647 ms 552 KB Partially correct
18 Partially correct 438 ms 636 KB Partially correct
19 Partially correct 495 ms 640 KB Partially correct
20 Partially correct 436 ms 784 KB Partially correct
21 Partially correct 62 ms 556 KB Partially correct
22 Partially correct 91 ms 656 KB Partially correct
23 Partially correct 114 ms 784 KB Partially correct
24 Partially correct 5 ms 596 KB Partially correct
25 Partially correct 6 ms 596 KB Partially correct
26 Partially correct 5 ms 596 KB Partially correct
27 Partially correct 4 ms 724 KB Partially correct
28 Partially correct 2 ms 600 KB Partially correct
29 Partially correct 562 ms 516 KB Partially correct
30 Partially correct 494 ms 644 KB Partially correct
31 Partially correct 494 ms 640 KB Partially correct
32 Partially correct 542 ms 528 KB Partially correct
33 Partially correct 510 ms 528 KB Partially correct
34 Partially correct 353 ms 608 KB Partially correct
35 Partially correct 446 ms 652 KB Partially correct
36 Partially correct 479 ms 720 KB Partially correct
37 Partially correct 467 ms 640 KB Partially correct
38 Partially correct 532 ms 848 KB Partially correct
39 Partially correct 466 ms 752 KB Partially correct
40 Partially correct 486 ms 916 KB Partially correct
41 Partially correct 477 ms 656 KB Partially correct
42 Partially correct 54 ms 704 KB Partially correct
43 Partially correct 106 ms 728 KB Partially correct
44 Partially correct 155 ms 528 KB Partially correct
45 Partially correct 166 ms 612 KB Partially correct
46 Partially correct 355 ms 592 KB Partially correct
47 Partially correct 335 ms 520 KB Partially correct
48 Partially correct 64 ms 732 KB Partially correct
49 Partially correct 70 ms 764 KB Partially correct