Submission #305093

#	Time	Username	Problem	Language	Result	Execution time	Memory
305093		Theo830	Stations (IOI20_stations)	C++14	100 / 100	1180 ms	1136 KiB

stations

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

#define f(i,a,b) for(ll i = a;i < b;i++)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define vll vector<ll>

#define pb push_back

///I hope I will get uprating and don't make mistakes

///I will never stop programming

///sqrt(-1) Love C++

///Please don't hack me

///@TheofanisOrfanou Theo830

///Training

vector<vll>adj;

ll tim = 0;

ll tin[1005];

ll tout[1005];

ll depth[1005];

void solve(ll s,ll p){

    tin[s] = tim;

    if(depth[s] % 2 == 0){

        tim++;

    }

    for(auto x:adj[s]){

        if(x != p){

            depth[x] = depth[s] + 1;

            solve(x,s);

        }

    }

    tout[s] = tim;

    if(depth[s] % 2){

        tim++;

    }

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

    ll m = u.size();

    adj.assign(n+5,vll());

    f(i,0,m){

        adj[u[i]].pb(v[i]);

        adj[v[i]].pb(u[i]);

    }

    tim = 0;

    depth[0] = 0;

    solve(0,-1);

    f(i,0,n){

        if(depth[i] % 2 == 0){

            labels[i] = tin[i];

        }

        else{

            labels[i] = tout[i];

        }

    }

    return labels;
}

bool isin(ll l,ll r,ll x){

    return (l <= x && x <= r);

}
int find_next_station(int s,int t,vector<int> c){

    ll tins,touts;

    if(s < c[0]){

        tins = s;

        touts = c.back();

        if(!isin(tins,touts,t)){

            return c.back();

        }

        else{

            for(auto x:c){

                if(t <= x){

                    return x;

                }

            }

        }

    }

    else{

        touts = s;

        tins = c[0];

        if(!isin(tins,touts,t)){

            return c[0];

        }

        else{

            reverse(c.begin(),c.end());

            for(auto x:c){

                if(x <= t){

                    return x;

                }

            }

        }

    }

    assert(0);
}

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