Submission #1167552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167552		who	기지국 (IOI20_stations)	C++20	0 / 100	3059 ms	2162688 KiB

stations

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

#define pb push_back

using namespace std;

static const int N = 1e3;

static int in[N+5], out[N+5], timer=0, h[N+5];
static vector<int> adj[N+5];

static void dfs(int par, int u)
{
    in[u] = ++timer;

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

        dfs(u, v);
    }

    out[u] = ++timer;
}

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


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

    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 function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
   92 | }
      | ^

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