Submission #578644

#	Time	Username	Problem	Language	Result	Execution time	Memory
578644		perchuts	Stations (IOI20_stations)	C++17	39 / 100	974 ms	772 KiB

stations

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

#include "stations.h"
vector<int>g[1001], labels;

int t = 0;

void dfs(int u,int p,bool entrada){
    if(entrada){
        labels[u] = t++;
    }
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u,entrada^1);
    }
    if(!entrada){
        labels[u] = t++;
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for(int i=0;i<n;++i){
        g[i].clear();
    }
    t = 0;
    for(int i=0;i<n-1;++i){
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    labels.resize(n);
    dfs(0,0,1);
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int m = sz(c);
    if(c[lower_bound(all(c),t)-begin(c)]==t)return t;//sou vizinho
    if(s>c[m-1]){//sou uma saida
        if(t>s||t<c[0])return c[0];//fora da subarvore
        return c[lower_bound(all(c),t) - begin(c) - 1];//ultimo cara que é menor
    }else{//sou uma entrada
        if(t>c[m-1]||t<s)return c[m-1];//fora da subarvore
        return c[lower_bound(all(c),t) - begin(c)];//primeiro cara que é maior
    }
}

// int main(){_
//     int n;cin>>n;
//     vector<int>u(n-1),v(n-1);
//     for(int i=0;i<n-1;++i){
//         cin>>u[i]>>v[i];
//     }    
//     vector<int>labels = label(n,n-1,u,v); 
//     // for(int i=1;i<=n;++i)printf("%d: %d\n",i-1,labels[i-1]);
//     cout<<find_next_station(1,3,{2,4})<<endl;
// }

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