Submission #1168780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168780		sitablechair	Stations (IOI20_stations)	C++20	0 / 100	301 ms	2916 KiB

stations

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

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

using namespace std;

const int N=100003;

int tdfs=0,tin[N*2],tout[N*2],d[N];
vector<int> big,ans,g[N];

void dfs(int u,int p=0) {
    tin[u]=++tdfs;
    for(auto v: g[u])
        if (v!=p) {
            d[v]=d[u]+1;
            dfs(v,u);
        }
    tout[u]=++tdfs;
}

vector<int> label(int n,int k,vector<int> u,vector<int> v) {
    ans.resize(n);
    For(i,0,n-1) g[i].clear();
    big.clear();
    tdfs=0;
    For(i,0,n-2) {
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    dfs(0);
    For(i,0,n-1)
        if (d[i]&1) big.pb(tin[i]);
        else big.pb(tout[i]);
    sort(all(big));
    unq(big);
    For(i,0,n-1)
        if (d[i]&1) ans[i]=lower_bound(all(big),tin[i])-big.begin();
        else ans[i]=lower_bound(all(big),tout[i])-big.begin();
    return ans;
}
int find_next_station(int s,int t,vector<int> c) {
    bool check=1;
    sort(all(c));
    for(auto u: c) {
        if (t==u) return t;
        if (u>s) check=0;
    }
    if (sz(c)==1) return c.back();
    if (check) {
        int mi=*min_element(all(c));
        int mi1=2e9;
        for(auto u: c)
            if (u!=mi && u<mi1) mi1=u;
        if (t<s && t>mi1) {
            for(int i=0;i<sz(c);i++) {
                int nxt=(i==sz(c)-1?s-1:c[i+1]-1);
                if (t>c[i] && t<nxt) return c[i];
            }
        } else return mi;
    } else {
        int ma=*max_element(all(c));
        int ma1=-2e9;
        for(auto u: c)
            if (u!=ma && u>ma1) ma1=u;
        if (t>s && t<ma1) {
            for(int i=0;i<sz(c);i++) {
                int prv=(i==0?s+1:c[i-1]+1);
                if (t>prv && t<c[i]) return c[i];
            }
        } else return ma;
    }
    return 69;
}

/*int r,n,k,q;
vector<int> lb,u1,v1;

void solve() {
    cin >> n >> k;
    u1.resize(n);
    v1.resize(n);
    For(i,1,n-1)
        cin >> u1[i] >> v1[i];
    cin >> q;
    lb=label(n,k,u1,v1);
    while(q--) {
        int z,y;
        cin >> z >> y;
        cout << find_next_station(z,y,g[z]) << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> r;
    while(r--) solve();
    return 0;
}*/

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