Submission #781787

#	Time	Username	Problem	Language	Result	Execution time	Memory
781787		jasmin	Stations (IOI20_stations)	C++17	0 / 100	766 ms	676 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);

    //compression
    vector<pair<int,int> > comp;
    for(int i=0; i<n; i++){
        comp.push_back({lab[i], i});
    }
    sort(comp.begin(), comp.end());

    for(int i=0; i<n; i++){
        lab[comp[i].second]=i;
    }
    
    return lab;
}




int find_next_station(int s, int t, vector<int> c) {
    s*=2;
    t*=2;
    for(auto& e: c){
        e*=2;
    }
    
    if(c.size()==1){
        return c[0];
    }

    
    int pres=s;
    int posts=s;
    int p=-1;
    vector<int> children;
    if(c[0]<s){
        
        p = c[0];
        for(int i=1; i<(int)c.size(); i++){
            children.push_back(c[i]);
        }

        pres = children[0] -1;
    }
    else{
        
        p = c.back();
        for(int i=0; i<(int)c.size()-1; i++){
            children.push_back(c[i]);
        }

        posts = children.back() +1;
    }

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

        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;
}

int find_next_station2(int s, int t, vector<int> c) {
    if(c.size()==1){
        return c[0];
    }


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

        if(t<s || children.back()<t){
            return p;
        }
        int next=-1;
        for(int i=children.size(); i>=0; i--){
            if(t<=children[i]){
                next=children[i];
            }
        }
        return next;
   }
    else{
        
        p = c.back();
        for(int i=0; i<(int)c.size()-1; i++){
            children.push_back(c[i]);
        }

        if(t<children[0] || s<t){
            return p;
        }
        int next=-1;
        for(int i=0; i<(int)children.size(); i++){
            if(children[i]<=t){
                next=children[i];
            }
        }
    }

    return -1;
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station2(int, int, std::vector<int>)':
stations.cpp:160:13: warning: variable 'next' set but not used [-Wunused-but-set-variable]
  160 |         int next=-1;
      |             ^~~~

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