제출 #1296236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296236		eri16	기지국 (IOI20_stations)	C++20	16 / 100	392 ms	516 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v) {

    vector<vector<int>> adj(n+1); 
    for(int i=0;i<n-1;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    vector<int> lbl(n);
    
    int ans=0;
    
    for (int i=0; i<n; i++){
        if (adj[i].size()>2){ans=i;}
    }
    
    queue <pair<int,pair<int,int>>> q;
    
    int visited[n]={0};
    
    visited[ans]=1;
    lbl[ans]=0;
    
    for (int i=0; i<adj[ans].size(); i++){
        q.push({adj[ans][i],{i+1,1}});
    }
    
    while (q.size()){
        
        auto x = q.front();
        q.pop();
        
        int node=x.first;
        int depth=x.second.second;
        int color=x.second.first;
        
        if (visited[node]==0){
            visited[node]=1;
            lbl[node]=color*1000+depth;
            for (int i=0; i<adj[node].size(); i++){
                q.push({adj[node][i],{color,depth+1}});
            }
        }
        
    }
    
    return lbl;
}

int find_next_station(int s, int t, vector <int> cp){

    if (s==0){

        for (int i=0; i<cp.size(); i++){
            if (cp[i]/1000==t/1000){return cp[i];}
        }
        return cp[0];
    }
    else if(s/1000!=t/1000){
        return cp[0];
    }
    else{
        if(t<s){
            return cp[0];
        }
        else{
            return cp[1];
        }            
    }
    return cp[0];
}

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