Submission #1262174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262174		gary	Stations (IOI20_stations)	C++20	100 / 100	306 ms	588 KiB

stations

// Jaskinia

// zadanko ..
// hm..

#include "stations.h"
#include <bits/stdc++.h>

#define GARY_LIB
// #define GARY_DBG
#ifdef GARY_DBG

#ifndef GARY_LIB
#include <bits/stdc++.h>
#endif

// --- ANSI Color Codes ---
#define RESET "\033[0m"
#define RED "\033[31m" /* Red */
#define GREEN "\033[32m" /* Green */
#define YELLOW "\033[33m" /* Yellow */
#define BLUE "\033[34m" /* Blue */
#define MAGENTA "\033[35m" /* Magenta */
#define CYAN "\033[36m" /* Cyan */

// Overload for std::pair
template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

// For std::tuple
template<typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) {
    os << '(';
    std::apply(
        [&os](const auto&... args) {
            bool first = true;
            ((os << (first ? "" : ", ") << args, first = false), ...);
        },
        t);
    return os << ')';
}

//  For std::bitset
template<size_t N>
std::ostream& operator<<(std::ostream& os, const std::bitset<N>& b) {
    return os << "bitset{" << b.to_string() << "}";
}

// Helper trait to detect if a type is a string
template<typename T>
struct is_string : std::false_type {};
template<>
struct is_string<std::string> : std::true_type {};
template<>
struct is_string<const char*> : std::true_type {};
template<>
struct is_string<char*> : std::true_type {};

// Overload for std::stack
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::stack<T, Container> s) {
    os << "stack{top: ";
    bool first = true;
    while (!s.empty()) {
        if (!first) os << ", ";
        first = false;
        os << s.top();
        s.pop();
    }
    os << '}';
    return os;
}

// Overload for std::queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::queue<T, Container> q) {
    os << "queue{front: ";
    bool first = true;
    while (!q.empty()) {
        if (!first) os << ", ";
        first = false;
        os << q.front();
        q.pop();
    }
    os << '}';
    return os;
}

// Overload for std::priority_queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container, typename Compare>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T, Container, Compare> pq) {
    os << "pq{top: ";
    bool first = true;
    while (!pq.empty()) {
        if (!first) os << ", ";
        first = false;
        os << pq.top();
        pq.pop();
    }
    os << '}';
    return os;
}

// Overload for containers (like vector, list, set, map, and deque) excluding strings
template<typename Container, typename std::enable_if<!is_string<Container>::value && !std::is_same<Container, std::string>::value &&
                                                         !std::is_same<Container, const char*>::value && !std::is_same<Container, char*>::value &&
                                                         !std::is_same<typename Container::value_type, char>::value,
                                                     int>::type = 0>
std::ostream& operator<<(std::ostream& os, const Container& container) {
    os << '{';
    bool first = true;
    for (const auto& elem : container) {
        if (!first) os << ", ";
        first = false;
        os << elem;
    }
    os << '}';
    return os;
}

// Helper to print multiple arguments (tuple unpacking trick)
template<size_t Index = 0, typename... Ts>
typename std::enable_if<Index == sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>&) {
}

template<size_t Index = 0, typename... Ts>
    typename std::enable_if < Index<sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>& t) {
    if (Index > 0) std::cerr << ", ";
    std::cerr << std::get<Index>(t);
    print_tuple<Index + 1>(t);
}

// Debug macro
#define debug(...)                                                                                                 \
    do {                                                                                                           \
        std::cerr << MAGENTA << "[" << __FILE__ << ":" << __LINE__ << " (" << __func__ << ")]" << RESET << " -> "; \
        std::cerr << "[" << #__VA_ARGS__ << "] ~> [";                                                              \
        print_tuple(std::make_tuple(__VA_ARGS__));                                                                 \
        std::cerr << "]" << std::endl;                                                                             \
    } while (0)
#else
#define debug(...) ((void)0)
#endif

constexpr int sizik = 1007;

int visited[sizik];
int val[sizik];

std::vector<int> kra[sizik];

int cnt = 0;
void DFS(int v, int W) {
    if (visited[v]) return;
    visited[v] = true;
    val[v] = W;
    if (W == 0) {
        val[v] = cnt++;
    }
    for (const auto& u : kra[v]) {
        DFS(u, W ^ 1);
    }
    if (W == 1) {
        val[v] = cnt++;
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    debug(n);
    std::vector<int> labels(n);

    for (int i = 0; i <= n; i++) {
        visited[i] = false;
        val[i] = 0;
        kra[i].clear();
        cnt = 0;
    }

#ifdef GARY_DBG
    debug("hi");
    std::cout << std::endl;
#endif

    // zwykly DFS w sumie ziomek ..
    // for (auto [a, b] : edges) {
    //     a++, b++;
    //     kra[a].push_back(b);
    //     kra[b].push_back(a);
    // }
    for (int i = 0; i < n - 1; i++) {
        int a = u[i] + 1, b = v[i] + 1;
        kra[a].push_back(b);
        kra[b].push_back(a);
    }

#ifdef GARY_DBG
    debug("przed DFS");
    std::cout << std::endl;
#endif
    DFS(1, 0);
#ifdef GARY_DBG
    debug("po DFS");
    std::cout << std::endl;
#endif

    for (int i = 0; i < n; i++) {
        labels[i] = val[i + 1];
// std::cout << "LABEL " << i + 1 << " ~> " << v[i + 1];
#ifdef GARY_DBG
        debug("LABEL", i + 1, val[i + 1]);
        std::cout << std::endl;
#endif
    }

    return labels;
}

/**
 *
 *
 */

int find_next_station(int v, int u, std::vector<int> c) {
    /**
     *
     * teraz trzeba odkodować belek...
     *
     */

    debug(v, u, c);

    // sprawdz czy ktorys ze sąsiadów nie jest szukany
    for (const auto& a : c) {
        if (a == u) {
            debug("MA ZIOMKA", a);
            return a;
        }
    }

    /**
     *
     * posortuj (na wszelki wypadek)
     */
    std::sort(c.begin(), c.end());

    // int who_am_i = -1;
    // jesli jest ziomek rowny 1 to jest korzeniem btw

    constexpr int PRE = 0, POST = 1;

    int who_am_i = PRE;
    if (c[0] < v) {
        who_am_i = POST;
    }

    debug(PRE, POST, who_am_i);

    // 0 -> pre ; 1 -> post ;

    // ojciec
    int o = -1;

    int ans = -1;

    if (v == 0) {
        // nie ma ojca!
    } else {
        if (who_am_i == POST) {
            o = c[0];
        } else {
            o = c[(int)c.size() - 1];
        }
    }

    debug(o);

    // czeakj ...45

    int local_pre = -1, local_post = -1;

    if (who_am_i == POST) {
        local_post = v;
        if (c.size() == 1)
            local_pre = local_post - 1;
        else
            local_pre = c[1] - 1;
    } else {
        // who_am_i == PRE
        local_pre = v;
        if (o == -1)
            local_post = c[(int)c.size() - 1] + 1;
        else if (c.size() == 1)
            local_post = local_pre + 1;
        else
            local_post = c[(int)c.size() - 2] + 1;
    }

    if (u > local_pre && u < local_post) {
    } else {
        // idz do ojca kurde mol
        return o;
    }

    // wiemy ze jest w którymś dziecku do zbója!

    if (who_am_i == PRE) {
        // czy jest w tym dziecku?
        std::reverse(c.begin(), c.end());
        int g = -1;
        for (const auto& a : c) {
            if (a == o) continue;
            if (u <= a) g = a;
        }
        return g;
    } else {
        // who_am_i == POST
        int g = -1;
        for (const auto& a : c) {
            if (a == o) continue;
            if (u >= a) g = a;
        }
        return g;
    }

    return ans;
}

/**
 *
 *
 *
void BFS() {
    int start = 1;
    std::queue<std::pair<int, int>> q;

    int cnt = 0;

    // 0 ~> pre ; 1 ~> post
    q.push({1, 0});
    while (!q.empty()) {
        const auto [v, W] = q.front();
        q.pop();

        if (visited[v]) continue;
        visited[v] = true;

        if (W == 0) {
            val[v] = cnt++;
        }

        for (const auto& u : kra[v]) {
            q.push({u, W ^ 1});
        }

        if (W == 1) {
            val[v] = cnt++;
        }
    }
}

 *
 */

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