제출 #1247182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247182		nikulid	기지국 (IOI20_stations)	C++20	5 / 100	307 ms	496 KiB

stations

#include <iostream>
#include <queue>

#include "stations.h"
#include <vector>

bool debug=0;

using namespace std;

#define pb push_back
#define mp make_pair

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    // subtask 1: line city
    vector<vector<int>> adj(n);
    for(int i=0; i<n-1; i++){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }
    // find edge
    int cur=0;
    for(int i=0; i<n; i++){
        if(adj[i].size()==1){
            // this an edge!
            cur = i;
            break;
        }
    }

    vector<int> labels(n, -1);
    queue<int> q;
    q.push(cur);
    int cnt=0;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        labels[cur] = cnt;
        cnt++;
        for(int e:adj[cur]){
            if(labels[e] == -1){
                q.push(e);
            }
        }
    }
    
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if(s<t){
        return s+1;
    } else{
        return s-1;
    }
}

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