Submission #1209737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209737		tosivanmak	Stations (IOI20_stations)	C++20	0 / 100	310 ms	560 KiB

stations

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll ord[1005]; bool vis[1005]; ll timer=0;
vector<ll>adj[1005];
void dfs(ll s, bool pref){
    vis[s]=1;
    if(pref){
        ord[s]=timer++;
    }
    for(auto& u: adj[s]){
        if(!vis[u]){
            dfs(u,!pref);
        }
    }
    if(!pref)ord[s]=timer++;
}

vector<int> label(int n, int k, vector<int>u, vector<int>v){
    for(int i=0;i<n;i++){
        adj[i].clear(); vis[i]=0; timer=0;ord[i]=0;
    }
    for(int i=0;i<n-1;i++){
        adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]);
    }
    dfs(0,1);
    vector<int>rd(n);
    for(int i=0;i<n;i++)rd[i]=ord[i]; return rd;
}
int find_next_station(int s, int t, vector<int>c){
    if(c.size()==0){
        return c[0];
    }
    if(s==0){
        vector<pair<ll,ll> >alls;
        for(int i=0;i<c.size();i++){
            if(i==0)alls.push_back({1,c[i]});
            else alls.push_back({c[i-1]+1,c[i]});
        }
        for(int i=0;i<alls.size();i++){
            if(alls[i].first<=t&&t<=alls[i].second)return alls[i].second;
        }
        return -1;
    }
    else{
        if(s<c[0]){
            // prefix
            ll lst=c[c.size()-1];
            c.pop_back();
            for(int i=0;i<c.size();i++){
                if(i==0){
                    if(s<=t&&t<=c[i]-1)return c[i];
                }
                else{
                    if(c[i-1]<=t&&t<=c[i]-1)return c[i];
                }
            }
            return lst;
        }
        else{
            // suffix
            ll lst=c[0]; reverse(c.begin(),c.end()); c.pop_back(); reverse(c.begin(),c.end());
            for(int i=0;i<c.size();i++){
                if(i==(int)c.size()-1){
                    if(c[i]<=t&&t<=s-1)return c[i];
                }
                else{
                    if(c[i]<=t&&t<=c[i+1]-1)return c[i];
                }
            }
            return lst;
        }
    }
}
// int main(){
//     ll n;
//     cin>>n;
//     vector<int>eu,ev;
//     for(int i=1;i<n;i++){
//         ll u,v;
//         cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u);
//         eu.push_back(u); ev.push_back(v);
//     }
//     label(n,10000,eu,ev);
//     for(int i=0;i<n;i++){
//         cout<<ord[i]<<" ";
//     }
//     cout<<'\n';
//     while(1){
//         ll psu,psv; vector<int>neighbours;
//         cin>>psu>>psv;
//         ll ncount; cin>>ncount;
//         for(int i=1;i<=ncount;i++){
//             ll th; cin>>th; neighbours.push_back(th);
//         }
//         cout<<find_next_station(psu,psv,neighbours)<<"\n";
//     }
// }

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