Submission #631677

#	Time	Username	Problem	Language	Result	Execution time	Memory
631677		MasterTaster	Stations (IOI20_stations)	C++14	52.32 / 100	830 ms	792 KiB

stations

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

#define pb push_back
#define MAXN 1010

using namespace std;

vector<int> g[MAXN];
int in, out, tin[MAXN], tout[MAXN];
bool bio[MAXN];

void dfs(int u)
{
    bio[u]=true;
    tin[u]=in++;
    for (auto v:g[u])
    {
        if (!bio[v]) dfs(v);
    }
    tout[u]=out++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for (int i=0; i<n; i++) { g[i].clear(); bio[i]=false; }
    in=out=0;
    for (int i=0; i<n-1; i++) { g[u[i]].pb(v[i]); g[v[i]].pb(u[i]); }
    dfs(0);

    vector<int> ret;
    for (int i=0; i<n; i++)
    {
        //cout<<i<<" "<<tin[i]<<" "<<tout[i]<<endl;
        ret.pb(tin[i]*1000+tout[i]);
        //cout<<ret[ret.size()-1]<<endl;
    }
    return ret;
}

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

    //for (int i=0; i<c.size(); i++) cout<<c[i]<<" s ";
    //cout<<endl;

    int in1, in2, out1, out2;
    in1=s/1000; in2=t/1000;
    out1=s%1000; out2=t%1000;

    //cout<<"s: "<<in1<<" "<<out1<<endl;
    //cout<<"t: "<<in2<<" "<<out2<<endl;

    if (in1<=in2 && out1>=out2)
    {
        //cout<<"DA"<<endl;
        for (int u:c)
        {
            int in3, out3;
            in3=u/1000; out3=u%1000;
            //cout<<u<<" jedan"<<endl;
            if (in3<=in2 && out3>=out2 && in1<=in3 && out1>=out3) {  return u; }
        }
    }
    else
    {
        for (int u:c)
        {
            int in3, out3;
            in3=u/1000; out3=u%1000;
            if (in3<=in1 && out3>=out1) return u;
        }
    }

}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

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