Submission #609196

#	Time	Username	Problem	Language	Result	Execution time	Memory
609196		Mher	Stations (IOI20_stations)	C++14	100 / 100	1059 ms	916 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
#include <vector>

using namespace std;

int sz;
vector<vector<int>> g;
vector<int> labels;
int cnt = 0;

void dfs(int v, int p)
{
    int tin = cnt++;
    for (int to : g[v])
    {
        if (to == p)
            continue;

        dfs(to, v);
    }
    int tout = cnt++;
    labels[v] = (tin % 2 == 0 ? tin : tout) / 2;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	labels = vector<int>(n);
	sz = n;
	g = vector<vector<int>>(n);
	cnt = 0;
	for (int i = 0; i < n - 1; i++)
    {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0, -1);
    return labels;
}

bool check(double tin, double tout, int m)
{
    return tin <= m && tout >= m;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s == 0)
    {
        for (int i = 1; i < c.size(); i++)
        {
            if (check(c[i - 1] + .5, c[i], t))
                return c[i];
        }
        return c[0];
    }
    else if (s > c[0])
    {
        if (!check(c[1] - .5, s, t))
            return c[0];

        for (int i = 1; i < c.size() - 1; i++)
        {
            if (check(c[i], c[i + 1] - .5, t))
                return c[i];
        }
        return c[c.size() - 1];
    }
    else
    {
        if (!check(s, c[c.size() - 2] + .5, t))
            return c[c.size() - 1];

        for (int i = 1; i < c.size() - .5; i++)
        {
            if (check(c[i - 1] + .5, c[i], t))
                return c[i];
        }
        return c[0];
    }
}

/*
1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3

*/

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 1; i < c.size(); i++)
      |                         ~~^~~~~~~~~~
stations.cpp:60:27: 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 = 1; i < c.size() - 1; i++)
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61