Submission #781676

#	Time	Username	Problem	Language	Result	Execution time	Memory
781676		jasmin	Stations (IOI20_stations)	C++17	0 / 100	776 ms	632 KiB

stations

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

int ind=0;
void dfs(int v, int p, int h, vector<vector<int> >& adi, vector<int>& lab){

    if(h%2==0){
        lab[v]=ind;
    }
    ind++;

    for(auto u: adi[v]){
        if(u==p) continue;

        dfs(u, v, h+1, adi, lab);
    }

    if(h%2==1){
        lab[v]=ind;
    }
    ind++;
}

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

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

    ind=0;
    vector<int> lab(n, -1);
    dfs(0, -1, 0, adi, lab);

    return lab;
}


int find_next_station(int s, int t, vector<int> c) {
    int p=c[0];
    vector<int> children;
    for(int i=1; i<(int)c.size(); i++){
        children.push_back(c[i]);
    }

    if(s==0){
        p=-1;
        children = c;
    }

    if(children.empty()){
        return p;
    }
    
    int pres=s;
    int posts=s;
    if(c[0]<s){
        pres = children[0]-1;
    }
    else{
        posts = children.back()+1;
    }

    if(t<pres || posts<t){
        return p;
    }

    int next=-1;
    if(c[0] < s){

        next=children[0];
        for(auto e: children){
            if(e<=t){
                next=e;
            }
        }

    }
    else{

        next=children.back();
        for(int i=children.size(); i>=0; i--){
            if(t<=children[i]){
                next=children[i];
            }
        }

    }
    return next;
}

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