Submission #1167555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167555		who	Stations (IOI20_stations)	C++20	0 / 100	0 ms	500 KiB

stations

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

#define pb push_back

using namespace std;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v)
{
    //cerr << n << ' ' << k << endl;
    vector<vector<int>> adj(n);
    for (int i=0; i<n-1; i++)
    {
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }

    vector<int> in(n, 0), out(n, 0), h(n, 0);
    int timer = 0;

    auto dfs = [&](auto self, int par, int u) -> int
    {
        in[u] = ++timer;

        for (int v : adj[u])
        {
            if (v == par) continue;
            h[v] = h[u] + 1;

            self(self, u, v);
        }

        out[u] = ++timer;
    };

    vector<int> res(n);
    vector<int> compress(n);

    dfs(dfs, 0, 0);

    for (int i=0; i<n; i++)
    {
        if (h[i] & 1) res[i] = out[i];
        else res[i] = in[i];

        compress[i] = res[i];
    }

    sort(compress.begin(), compress.end());

    for (int i=0; i<n; i++) res[i] = lower_bound(compress.begin(), compress.end(), res[i]) - compress.begin();

    return res;
}


int find_next_station(int s, int t, std::vector<int> c) {
	if (c.size() == 1) return c[0];
	for (int i : c)
    {
        if (t == i) return i;
    }

    if (s == 0)
    {
        for (int i=0; i<c.size(); i++)
        {
            if (t < c[i]) return c[i];
        }
    } else if (c[0] > s) //s is "in"
    {
        c.insert(c.begin(), s);
        for (int i=1; i<c.size()-1; i++)
        {
            if (c[i-1] < t && t < c[i]) return c[i];
        }

        return c.back();
    } else
    {
        c.push_back(s);

        for (int i=1; i<c.size()-1; i++)
        {
            if (c[i+1] > t && t > c[i]) return c[i];
        }

        return c.front();
    }
}

Compilation message (stderr)

stations.cpp: In lambda function:
stations.cpp:34:5: warning: no return statement in function returning non-void [-Wreturn-type]
   34 |     };
      |     ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

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