oj.uz

Submission #432365

# Submission time Handle Problem Language Result Execution time Memory
432365 2021-06-18T08:35:27 Z idk321 Stations (IOI20_stations) C++17
10 / 100
 932 ms 656 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++;
}





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] + 1000;
        else labels[i] = out[i];
    }
    return labels;
}



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


        if (t < s) return par;

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

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

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


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


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

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

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






    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

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 316 KB Invalid labels (duplicates values). scenario=1, label=1300
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 508 KB Output is correct
2 Correct 698 ms 656 KB Output is correct
3 Correct 695 ms 508 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 610 ms 516 KB Output is correct
8 Correct 932 ms 580 KB Output is correct
9 Correct 643 ms 528 KB Output is correct
10 Correct 609 ms 640 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 4 ms 600 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 503 ms 528 KB Output is correct
17 Correct 518 ms 512 KB Output is correct
18 Correct 495 ms 656 KB Output is correct
19 Correct 527 ms 528 KB Output is correct
20 Correct 541 ms 400 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 328 KB Invalid labels (duplicates values). scenario=1, label=1834
2 Halted 0 ms 0 KB -