제출 #1311265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311265		altayeb_132	Stations (IOI20_stations)	C++20	100 / 100	407 ms	616 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()
#define pb push_back
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);
    map<int, int> mp;
    vector<int> v1;
    int cnt = 0;
    for (int i = 0; i < n; i++) 
    {
        labels[i] = ((dpth[i] % 2)? dt[i] : ft[i]);
        v1.pb(labels[i]);
    }
    sort(all(v1));
    int nm = 0;
    mp[v1[0]] = nm;
    for(int i = 1; i < n; i++)
    {
        if(v1[i] != v1[i - 1])
            mp[v1[i]] = ++nm;
    }
    for(int i = 0; i < n; i++)
        labels[i] = mp[labels[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: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61