제출 #1311244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311244		moha1111	기지국 (IOI20_stations)	C++20	100 / 100	397 ms	576 KiB

stations

#include "bits/stdc++.h"
#include "stations.h"
using namespace std;

int tt;

void dfs(int node , vector<int>& lab , vector<vector<int>>& graph , bool dip , vector<int> &vis)
{
    if(dip == 0)
        lab[node] = tt , tt++;
        
    vis[node] = 1;
    for(auto i : graph[node])
    {
        if(vis[i] == 0)
            dfs(i , lab , graph , dip ^ 1 , vis);
    }
    if(dip == 1)
        lab[node] = tt , tt++;
        
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    tt = 0;
    vector<vector<int>> graph(n + 5);
    for(int i = 0 ; i < n - 1 ; i++)
    {
        graph[u[i]].push_back(v[i]);
        graph[v[i]].push_back(u[i]);
    }
    vector<int> lab(n) , vis(n , 0);
    dfs(0 , lab , graph , 0 , vis);
    return lab;
}

int find_next_station(int s, int t, vector<int> c)
{
    if(c.size() == 1)
        return c[0];
    
    if(s < c[0])
    {
        /// start
        int p = -1;
        for(int i = 0 ; i < c.size() - 1 ; i++)
        {
            int st , en = c[i];
            if(p == -1)
                st = s + 1;
            
            else
                st = p + 1;
            
            if(st <= t && t <= en)
                return c[i];
            
            p = c[i];
        }
        return c.back();
    }
    /// end
    int p = -1;
    for(int i = c.size() - 1 ; i >= 1 ; i--)
    {
        int st = c[i] , en;
        if(p == -1)
            en = s - 1;
        
        else
            en = p - 1;
        
        if(st <= t && t <= en)
            return c[i];
        
        p = c[i];
    }
    return c[0];
}

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