Submission #306819

#	Time	Username	Problem	Language	Result	Execution time	Memory
306819		nicolaalexandra	Stations (IOI20_stations)	C++14	76 / 100	1055 ms	1168 KiB

stations

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

vector <int> L[DIM];
int viz[DIM],level[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]){
            level[vecin] = 1 + level[nod];
            dfs (vecin);
        }
    poz[nod].second = ++idx;
}

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);
    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);
    }

    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();
    }

}

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