Submission #306854

#	Time	Username	Problem	Language	Result	Execution time	Memory
306854		nicolaalexandra	Stations (IOI20_stations)	C++14	100 / 100	915 ms	1280 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
#define DIM 1010
using namespace std;

vector <int> L[DIM],aux;
int viz[DIM],level[DIM],fth[DIM];
pair <int,int> poz[DIM];
int idx;

void dfs (int nod){

    viz[nod] = 1;
    poz[nod].first = ++idx;
    for (auto vecin : L[nod])
        if (!viz[vecin]){
            fth[vecin] = nod;
            level[vecin] = 1 + level[nod];
            dfs (vecin);
        }
    poz[nod].second = ++idx;
}

int cautare_binara (int n, int val){
    int st = 0, dr = n-1;
    while (st <= dr){
        int mid = (st + dr)>>1;
        if (aux[mid] == val)
            return mid;
        if (aux[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
}

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

    for (i=0;i<n;i++)
        L[i].clear();

    for (i=0;i<n-1;i++){
        int x = u[i], y = v[i];
        L[x].push_back(y);
        L[y].push_back(x);
    }

    memset (viz,0,sizeof viz);
    memset (level,0,sizeof level);
    memset (poz,0,sizeof poz);
    memset (fth,0,sizeof fth);

    idx = -1;

    dfs (0);

    vector <int> labels;
    for (i=0;i<n;i++){
        if (level[i] % 2 == 0)
            labels.push_back(poz[i].first);
        else labels.push_back(poz[i].second);
    }

    /// pot sa le normalizez??
    aux = labels;
    sort (aux.begin(),aux.end());
    for (i=0;i<n;i++)
        labels[i] = cautare_binara (n,labels[i]);

    return labels;

}

int find_next_station (int x, int y, vector <int> v){

    /// mai intai vad daca se afla pe un nivel par sau impar

    int ok = 0;
    for (auto it : v)
        if (it < x){
            ok = 1;
            break;
        }

    if (!ok){ /// labelul x inseamna de fapt un inceput de interval

        if (y < x)
            return v.back();

        for (auto it : v)
            if (y <= it)
                return it;

        return v.back();

    } else {

        if (y > x)
            return v.front();

        for (int i=v.size()-1;i>=0;i--)
            if (y >= v[i])
                return v[i];

        return v.front();
    }

}

Compilation message (stderr)

stations.cpp: In function 'int cautare_binara(int, int)':
stations.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

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