제출 #1311214

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

stations

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

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

    time++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    vector<vector<int>> graph(n + 5);
    for(int i = 1 ; i < n ; i++)
    {
        graph[u[i]].push_back(v[i]);
        graph[v[i]].push_back(u[i]);
    }
    vector<int> lab(n + 5) , vis(n + 5);
    dfs(0 , 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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61