Submission #546797

#	Time	Username	Problem	Language	Result	Execution time	Memory
546797		LucaDantas	Stations (IOI20_stations)	C++17	100 / 100	817 ms	868 KiB

stations

#include "stations.h"
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

constexpr int maxn = 1010;

std::vector<int> g[maxn];
int in[maxn], out[maxn], cor[maxn], t;

void dfs(int u, int p) {
    in[u] = t++;
    for(int v : g[u]) if(v != p) {
        cor[v] = cor[u]^1;
        dfs(v, u);
    }
    out[u] = t++;
}

void clear() {
    memset(in, 0, sizeof in);
    memset(out, 0, sizeof out);
    memset(cor, 0, sizeof cor);
    for(int i = 0; i < maxn; i++)
        g[i].clear();
    t = 0;
}

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

    std::map<int,int> mp;
    int coord = 0;
    for(int i = 0; i < n; i++)
        mp[!cor[i] ? in[i] : out[i]] = 0;
    for(auto& it : mp)
        it.second = coord++;

    std::vector<int> labels;
    for(int i = 0; i < n; i++)
        labels.push_back(mp[!cor[i] ? in[i] : out[i]]);
    
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(c[0] > s) {
        // sou in, todos os meus filhos são out
        if(t < s) return c.back();
        for(int x : c)
            if(t <= x) return x;
        return c.back();
    } else {
        // sou out, todos os meus filhos sao in
        std::reverse(c.begin(), c.end()); // comeco do meu ultimo filho
        if(t > s) return c.back(); // c.back() é o meu pai
        for(int x : c)
            if(t >= x) return x;
        return c.back();
    }
}

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