Submission #1140337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140337		Almonther	Stations (IOI20_stations)	C++20	100 / 100	300 ms	612 KiB

stations

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

#define ll long long
#define co cout<<
using namespace std;
//stuff
const ll maxn=1005;
ll a[maxn]={};
vector<ll>v1[maxn];
ll tim=0;
void dfs(ll x,ll last,ll dep){
    if(dep%2==0) a[x]=tim++;
    for(auto i:v1[x]){
        if(i!=last) dfs(i,x,dep+1);
    }
    if(dep%2) a[x]=tim++;
}
vector<int>label(int n, int k, vector<int> u, vector<int> v){
    for(int i=0;i<n;i++) v1[i].clear();
    for(int i=0;i<u.size();i++){
        v1[u[i]].push_back(v[i]);
        v1[v[i]].push_back(u[i]);
    }
    tim=0;
    dfs(0,-1,0);
    vector<int>labels;
    for(int i=0;i<n;i++) labels.push_back(a[i]);
    return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    if(s>c[0]){
        // i have the right
        if(s<t||t<c[0]) return c[0];
        // find the max
        int mx=0;
        for(int i=0;i<c.size();i++) if(t>=c[i]) mx=max(mx,c[i]);
        return mx;
    }
    // i have the left
    if(c.back()<t||t<s) return c.back();
    // find the min
    int mn=1e9;
    for(int i=0;i<c.size();i++) if(t<=c[i]) mn=min(mn,c[i]);
    return mn;
}

// int main(){
    // co find_next_station(1,3,{2,3,5});
    // co find_next_station(4,3,{2,1});
    // vector<int>smth=label(5,1000,{0,1,2,3},{1,2,3,4});
    // for(int i=0;i<smth.size();i++){
    //     co i<<' '<<smth[i]<<'\n';
    // }
// }

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