Submission #554873

#	Time	Username	Problem	Language	Result	Execution time	Memory
554873		status_coding	Stations (IOI20_stations)	C++14	100 / 100	825 ms	932 KiB

stations

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

using namespace std;

int t=0;
int d[1005], in[1005], out[5005];
vector<int> v[1005];

void dfs(int p, int par)
{
    t++;
    in[p] = t;

    if(par == -1)
        d[p] = 0;
    else
        d[p] = d[par] + 1;

    for(int it : v[p])
    {
        if(it == par)
            continue;

        dfs(it, p);
    }

    t++;
    out[p] = t;
}

void norm(vector<int> &v)
{
    map<int, int> fr;

    for(int it : v)
        fr[it] = 1;

    int nr = -1;
    for(auto &it : fr)
    {
        nr++;
        it.second = nr;
    }

    for(int &it : v)
        it = fr[it];
}

vector<int> label(int n, int k, vector<int> x, vector<int> y)
{
    for(int i=0; i<n; i++)
        v[i].clear();

    for(int i=0; i<(int)x.size(); i++)
    {
        v[ x[i] ].push_back( y[i] );
        v[ y[i] ].push_back( x[i] );
    }

    dfs(0, -1);

    vector<int> ans;
    for(int i=0; i<n; i++)
    {
        if(d[i] % 2 == 0)
            ans.push_back(in[i]);
        else
            ans.push_back(out[i]);
    }

    norm(ans);
    return ans;
}

int find_next_station(int s, int t, vector<int> v)
{
    if(v.size() == 1)
        return v[0];

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

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

        return v[0];
    }

    if(s < v[0])
    {
        /// is in

        int l = s;
        int r = v[(int)v.size() - 2];

        if(l <= t && t <= r)
        {
            for(int i=0; i<(int)v.size()-1 ; i++)
                if(v[i] >= t)
                    return v[i];
        }
        else
            return v.back();
    }
    else
    {
        /// is out

        int l = v[1];
        int r = s;

        if(l <= t && t<=r)
        {
            for(int i=(int)v.size()-1; i>=1; i--)
                if(v[i] <= t)
                    return v[i];
        }
        else
            return v[0];
    }
}

Compilation message (stderr)

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

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