Test/UC/4-17-K.test.cpp

• View this file on GitHub
• Last update: 2026-02-22 16:34:07+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb
• Link: https://contest.ucup.ac/contest/3384/problem/17171
• Link: https://contest.ucup.ac/submission/2053140

Depends on

• Eulerian Trail (オイラー路) (Src/Graph/EulerianTrail.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

// #define PROBLEM "https://contest.ucup.ac/contest/3384/problem/17171"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

/*
 * GP of St. Petersburg K. Traversal of a Triangular Grid
 * https://contest.ucup.ac/submission/2053140
 */

#include "../../Src/Graph/EulerianTrail.hpp"
using namespace zawa;
#include <algorithm>
#include <iostream>
#include <ranges>
#include <utility>
#include <vector>
using namespace std;
int main() {
#ifdef ONLINE_JUDGE
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N;
    cin >> N;
    vector<pair<int,int>> p;
    for (int i = 0 ; i <= N ; i++)
        for (int j = 0 ; j <= i ; j++)
            p.push_back({i,j});
    vector<pair<int,int>> E, dir;
    for (int i = 0 ; i <= N ; i++)
        for (int j = 0 ; j <= i ; j++) {
            const int u = ranges::find(p,pair{i,j}) - p.begin();
            if (j + 1 <= i) {
                const int v = ranges::find(p,pair{i,j+1}) - p.begin();
                E.push_back({u,v});
                dir.push_back({0,3});
            }
            if (i + 1 <= N) {
                const int v = ranges::find(p,pair{i+1,j}) - p.begin();
                E.push_back({u,v});
                dir.push_back({4,1});
            }
            if (i + 1 <= N) {
                const int v = ranges::find(p,pair{i+1,j+1}) - p.begin();
                E.push_back({u,v});
                dir.push_back({5,2});
            }
        }
    const int s = ranges::find(p,pair{0,0}) - p.begin();
    auto [vs, es] = *EulerianTrail((int)p.size(),E,false,s);
    // for (int i : vs)
    //     cout << '(' << p[i].first << ',' << p[i].second << ')';
    // cout << endl;
    for (int i = 0 ; i < ssize(es) ; i++) {
        int u = vs[i], v = vs[i+1];
        if (E[es[i]] == pair{u,v})
            cout << dir[es[i]].first;
        else if (E[es[i]] == pair{v,u})
            cout << dir[es[i]].second;
        else
            assert(0);
    }
    cout << '\n';
#else
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
#endif
}

#line 1 "Test/UC/4-17-K.test.cpp"
// #define PROBLEM "https://contest.ucup.ac/contest/3384/problem/17171"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

/*
 * GP of St. Petersburg K. Traversal of a Triangular Grid
 * https://contest.ucup.ac/submission/2053140
 */

#line 2 "Src/Graph/EulerianTrail.hpp"

#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 10 "Src/Graph/EulerianTrail.hpp"

namespace zawa {

// first: vertices, second: edge id
template <class T>
std::optional<std::pair<std::vector<T>, std::vector<usize>>> EulerianTrail(T n, const std::vector<std::pair<T, T>>& edges, bool directed, T start = -1) {
    if (start != static_cast<T>(-1))
        assert(start < n);
    std::vector<std::vector<std::pair<T, usize>>> g(n);
    for (usize i = 0 ; auto [u, v] : edges) {
        assert(u < n and v < n);
        g[u].push_back({v, i});
        if (!directed) 
            g[v].push_back({u, i});
        i++;
    }
    T st = edges.empty() ? T{0} : edges[0].first, go = st;
    if (directed) {
        std::vector<i32> deg(n);
        for (auto [u, v] : edges) {
            deg[u]++;
            deg[v]--;
        }
        bool fnst = false, fngo = false;
        for (T i = 0 ; i < n ; i++) {
            if (deg[i] == 1) {
                if (fnst) 
                    return std::nullopt;
                fnst = true;
                st = i;
            }
            else if (deg[i] == -1) {
                if (fngo) 
                    return std::nullopt;
                fngo = true;
                go = i;
            }
            else if (deg[i]) 
                return std::nullopt;
        }
        if (start != static_cast<T>(-1)) {
            if (fnst and st != start)
                return std::nullopt;
            if (!fnst)
                st = go = start;
        }
    }
    else {
        usize cntOdd = 0;
        for (T i = 0 ; i < n ; i++) 
            if (g[i].size() & 1)
                (cntOdd++ ? go : st) = i;
        if (cntOdd != 0 and cntOdd != 2) 
            return std::nullopt;
        if (start != static_cast<T>(-1)) {
            if (cntOdd == 0)
                st = go = start;
            else if (go == start)
                std::swap(st,go);
            else if (st != start)
                return std::nullopt;
        }
    }
    std::vector<bool> used(edges.size());
    std::vector<usize> cur(n), es;
    std::vector<T> vs;
    auto dfs = [&](auto dfs, const T v) -> void {
        while (cur[v] < g[v].size()) {
            auto [x, i] = g[v][cur[v]++];
            if (!used[i]) {
                used[i] = true;
                dfs(dfs, x);
                es.push_back(i);
                vs.push_back(v);
            }
        }
    };
    dfs(dfs, st);
    std::ranges::reverse(vs);
    vs.push_back(go);
    std::ranges::reverse(es);
    if (edges.size() != es.size()) 
        return std::nullopt;
    return std::make_pair(vs, es);
}

} // namespace zawa
#line 10 "Test/UC/4-17-K.test.cpp"
using namespace zawa;
#line 12 "Test/UC/4-17-K.test.cpp"
#include <iostream>
#include <ranges>
#line 16 "Test/UC/4-17-K.test.cpp"
using namespace std;
int main() {
#ifdef ONLINE_JUDGE
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N;
    cin >> N;
    vector<pair<int,int>> p;
    for (int i = 0 ; i <= N ; i++)
        for (int j = 0 ; j <= i ; j++)
            p.push_back({i,j});
    vector<pair<int,int>> E, dir;
    for (int i = 0 ; i <= N ; i++)
        for (int j = 0 ; j <= i ; j++) {
            const int u = ranges::find(p,pair{i,j}) - p.begin();
            if (j + 1 <= i) {
                const int v = ranges::find(p,pair{i,j+1}) - p.begin();
                E.push_back({u,v});
                dir.push_back({0,3});
            }
            if (i + 1 <= N) {
                const int v = ranges::find(p,pair{i+1,j}) - p.begin();
                E.push_back({u,v});
                dir.push_back({4,1});
            }
            if (i + 1 <= N) {
                const int v = ranges::find(p,pair{i+1,j+1}) - p.begin();
                E.push_back({u,v});
                dir.push_back({5,2});
            }
        }
    const int s = ranges::find(p,pair{0,0}) - p.begin();
    auto [vs, es] = *EulerianTrail((int)p.size(),E,false,s);
    // for (int i : vs)
    //     cout << '(' << p[i].first << ',' << p[i].second << ')';
    // cout << endl;
    for (int i = 0 ; i < ssize(es) ; i++) {
        int u = vs[i], v = vs[i+1];
        if (E[es[i]] == pair{u,v})
            cout << dir[es[i]].first;
        else if (E[es[i]] == pair{v,u})
            cout << dir[es[i]].second;
        else
            assert(0);
    }
    cout << '\n';
#else
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
#endif
}

Back to top page