Submission #1247163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247163		nikulid	Stations (IOI20_stations)	C++20	52.32 / 100	311 ms	612 KiB

stations

#include <iostream>

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

bool debug=0;

using namespace std;

#define pb push_back
#define mp make_pair

vector<vector<int>> adj;

vector<int> bl; // base labels (euler search)

int cur=0;
void dfs(int node){ // used to initialise `bl`
    bl[node] = cur;
    cur++;
    for(int e:adj[node]){
        if(bl[e]==-1){
            dfs(e);
        }
    }
    return;
}

vector<int> ml; // max-labels (max bl of all children)
int get_ml(int node){
    // if(ml[node]!=-1)return ml[node];

    int answer=bl[node];
    for(int e:adj[node]){
        if(bl[e]>bl[node]){ // is that a child?
            answer=max(answer, get_ml(e));
        }
    }
    ml[node] = answer;
    return ml[node];
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    bl = vector<int>(n, -1);
    ml = vector<int>(n, -1);
    adj = vector<vector<int>>(n);

    for(int i=0; i<n-1; i++){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }
    cur=0;
    dfs(0);
    get_ml(0);
	vector<int> labels(n);
    for(int i=0; i<n; i++){
        labels[i] = 1000*bl[i] + ml[i];
    }
    
    if(debug)
    {
        cout<<"$ LABELS ARE AS FOLLOWS:\n";
        for(int i=0; i<n; i++){
            cout<<labels[i]<<"\n";
        }
    }
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    for(int i=0; i<c.size(); i++){
        if(c[i] == t){
            return c[i];
        }
    }
    int target_base = t/1000;
    int this_base=s/1000, this_max=s%1000;
    int next_base, next_max;
    if(target_base < this_base || target_base > this_max){
        // we have to travel up (towards the root)
        return c[0];
    } else{
        // we have to travel down the tree
        for(int i=0; i<c.size(); i++){
            next_base = c[i]/1000;
            next_max = c[i]%1000;
            if(next_base < this_base)continue;// make sure it's not a parent node
            if(next_base <= target_base && next_max >= target_base){
                return c[i];
            }
        }
    }
    return c[0];
}

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