Submission #316197

#	Time	Username	Problem	Language	Result	Execution time	Memory
316197		ScarletS	Stations (IOI20_stations)	C++17	100 / 100	964 ms	1336 KiB

stations

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

const int maxn = 1e3;
int tin[maxn],tout[maxn],t;
vector<int> edges[maxn];
vector<pii> temp;

void dfs(int c, int p, bool h)
{
    tin[c]=++t;
    for (int i : edges[c])
        if (i!=p)
            dfs(i,c,h^1);
    tout[c]=++t;
    if (h)
        temp.push_back({tout[c],c});
    else
        temp.push_back({tin[c],c});
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector<int> labels(n);
    for (int i=0;i<n;++i)
        edges[i].clear();
    for (int i=0;i<n-1;++i)
    {
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    temp.clear();
    t=-1;
    dfs(0,-1,0);
    sort(temp.begin(), temp.end());
    for (int i=0;i<n;++i)
        labels[temp[i].s]=i;
    return labels;
}

int find_next_station(int a, int b, vector<int> c)
{
    int x = c.size();
    vector<pii> v;
    sort(c.begin(), c.end());
    if (a==0)
    {
        v.push_back({1,c[0]});
        for (int i=1;i<x;++i)
            v.push_back({c[i-1]+1,c[i]});
        for (pii i : v)
            if (i.f<=b&&b<=i.s)
                return i.s;
        while (1)
            ++a;
    }
    if (a<c[0])
    {
        if (x>1)
        {
            v.push_back({a+1,c[0]});
            if (a+1<=b&&b<=c[0])
                return c[0];
            for (int i=1;i<x-1;++i)
                if (c[i-1]+1<=b&&b<=c[i])
                    return c[i];
        }
        return c.back();
    }
    if (x>1)
    {
        if (c[x-1]<=b&&b<=a-1)
            return c[x-1];
        for (int i=x-2;i>=0;--i)
            if (c[i]<=b&&b<=c[i+1]-1)
                return c[i];
    }
    return c[0];
}
/**
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    return 0;
}
**/

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