Submission #720522

#	Time	Username	Problem	Language	Result	Execution time	Memory
720522		bin9638	Stations (IOI20_stations)	C++17	0 / 100	796 ms	2400 KiB

stations

#include <bits/stdc++.h>

#ifndef SKY
#include "stations.h"
#endif // SKY

using namespace std;

#define N 10010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n,k,times;
vector<int>g[N],kq;
ii cnt[N];

void DFS(int u,int p)
{
    cnt[u].fs=++times;
    for(auto v:g[u])
        if(v!=p)
            DFS(v,u);
    cnt[u].sc=++times;
}

void build(int u,int p,int id)
{
    if(id==0)
        kq[u]=cnt[u].fs;
            else kq[u]=cnt[u].sc;
    for(auto v:g[u])
        if(v!=p)
            build(v,u,(id^1));
}

vector<int> label(int dm, int vl, vector<int> canh_fs, vector<int> canh_sc)
{
    n=dm;
    k=vl;
    for(int i=0;i<n;i++)
        g[i].clear();
    kq.resize(n,0);
    times=0;
    for(int i=0;i<n-1;i++)
    {
        int u=canh_fs[i],v=canh_sc[i];
        g[u].pb(v);
        g[v].pb(u);
    }
    DFS(0,-1);
    build(0,-1,0);
    //for(int i=0;i<n;i++)cout<<kq[i]<<" ";cout<<endl;
    return kq;
}

int find_next_station(int u, int v, vector<int> s)
{
   // cout<<u<<endl;
  //  for(auto con:s)cout<<con<<endl;
    if(u==v)
    {
        while(1);
    }
    if(s.size()==1)
        return s[0];
    vector<ii>cnt;
    if(u<=*min_element(s.begin(),s.end()))
    {
       // sort(s.begin(),s.end());
        cnt.pb({u+1,s[0]});
        for(int i=1;(u!=1 ? i<s.size()-1 : s.size());i++)
           cnt.pb({s[i-1]+1,s[i]});
        assert(!cnt.empty());
        for(auto con:cnt)
            if(con.fs<=v&&con.sc>=v)
                return con.sc;
        return s.back();
    }else
    {
      //  cout<<"cc";
       // sort(s.begin(),s.end());
        cnt.pb({s.back(),u-1});
        for(int i=s.size()-2;i>=1;i--)
           cnt.pb({s[i],s[i+1]-1});
        assert(!cnt.empty());
        for(auto con:cnt)
            if(con.fs<=v&&con.sc>=v)
                return con.fs;
        return s[0];
    }
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    vector<int>u(n-1),v(n-1);
    for(int i=0;i<n-1;i++)
    {
        cin>>u[i]>>v[i];
    }
    vector<int>kq=label(n,k,u,v);
    for(int i=0;i<n;i++)cout<<kq[i]<<" ";cout<<endl;
    int S,T;
    cin>>S>>T;
    vector<int>s;
    for(auto v:g[S])
        s.pb(kq[v]);
    cout<<find_next_station(kq[S],kq[T],s);
    return 0;
}
#endif

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i=1;(u!=1 ? i<s.size()-1 : s.size());i++)
      |                             ~^~~~~~~~~~~

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