제출 #1311256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311256		altayeb_132	기지국 (IOI20_stations)	C++20	76 / 100	509 ms	568 KiB

stations

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1001];
int t1 = 0;
int dt[1001], ft[1001], dpth[1001];
int const INF = 1e9;
#define all(x) (x).begin(), x.end()
void dfs(int n, int pr, int dpt = 0)
{
    dpth[n] = dpt;
    dt[n] = t1++;
    for(auto i : adj[n])
        if(i != pr)
            dfs(i, n, dpt + 1);
    ft[n] = t1++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) 
{
    for(int i = 0; i < n; i++)
    {
        adj[i].clear();
        ft[i] = dt[i] = dpth[i] = 0;
    }
    t1 = 0;
    vector<int> labels(n);
    for(int i = 0; i < n - 1; i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0, -1);

    for (int i = 0; i < n; i++) 
    {
        labels[i] = ((dpth[i] % 2)? dt[i] : ft[i]);
    }
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) 
{
    int mn = INF, mx = 0, pr = 0;
    for(auto i : c)
    {
        mn = min(mn, i);
        mx = max(mx, i);
    }
    if(mn > s)
    {
        erase(c, mx);
        pr = mx;
        sort(all(c));
        int opn = s + 1;
        for(auto i : c)
        {
            if(t >= opn && t <= i)
            {
                return i;
            }
            opn = i + 1;
        }
    }
    else
    {
        erase(c, mn);
        pr = mn;
        sort(all(c));
        reverse(all(c));
        int cls = s - 1;
        for(auto i : c)
        {
            if(t <= cls && t >= i)
            {
                return i;
            }
            cls = i - 1;
        }
    }
    return pr;
}

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