Submission #537010

#	Time	Username	Problem	Language	Result	Execution time	Memory
537010		maomao90	Speedrun (RMI21_speedrun)	C++17	0 / 100	143 ms	940 KiB

speedrun

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "speedrun.h"
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
#define MAXL 20

void assignHints(int subtask, int n, int a[], int b[]) {
    vector<vi> adj(n + 5);
    REP (i, 1, n) {
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
    vi sib(n + 5, -1), chi(n + 5, -1);
    auto dfs = [&] (auto &&self, int u, int p) {
        if (0) {
            return;
        }
        REP (i, 0, adj[u].size()) {
            int v = adj[u][i];
            if (v == p) {
                swap(adj[u][i], adj[u][adj[u].size() - 1]);
                adj[u].pop_back();
                break;
            }
        }
        if (!adj[u].empty()) {
            chi[u] = adj[u][0];
        } else {
            chi[u] = 0;
        }
        REP (i, 0, adj[u].size()) {
            int v = adj[u][i];
            if (i + 1 < adj[u].size()) {
                sib[v] = adj[u][i + 1];
            } else {
                sib[v] = p;
            }
            self(self, v, u);
        }
        return;
    };
    sib[1] = 0;
    dfs(dfs, 1, (1 << (MAXL / 2)) - 1);
    setHintLen(MAXL);
    REP (i, 1, n + 1) {
        cerr << i << ": " << chi[i] << ' ' << sib[i] << '\n';
        assert(chi[i] != -1);
        REP (j, 0, MAXL / 2) {
            if (chi[i] >> j & 1) {
                setHint(i, j + 1, 1);
            }
        }
    }
    REP (i, 1, n + 1) {
        assert(sib[i] != -1);
        REP (j, 0, MAXL / 2) {
            if (sib[i] >> j & 1) {
                setHint(i, j + 1 + MAXL / 2, 1);
            }
        }
    }
}

void speedrun(int subtask, int n, int start) {
    auto get = [&] (bool sib) {
        int res = 0;
        REP (i, 0, MAXL / 2) {
            res |= getHint(i + 1 + sib * MAXL / 2) << i;
        }
        return res;
    };
    vi vis(n + 5, 0);
    auto isp = [&] (int u, int p) {
        if (p == (1 << (MAXL / 2)) - 1) {
            return 1;
        }
        if (p == 1) {
            return 1;
        }
        if (vis[u] == (1 << (MAXL / 2)) - 1) {
            return 0;
        }
        int sib = get(1);
        assert(sib > 0);
        assert(goTo(p));
        if (goTo(sib)) {
            assert(goTo(p));
            assert(goTo(u));
            return 1;
        } else {
            assert(goTo(u));
            return 0;
        }
    };
    auto dfs = [&] (auto &&self, int u, int p) {
        if (0) {
            return;
        }
        cerr << ' ' << u << ' ' << p << '\n';
        if (u == (1 << (MAXL / 2)) - 1) {
            return;
        }
        int chi = get(0), sib = get(1);
        vis[u] = sib;
        if (chi == 0) {
            assert(p != -1);
            assert(goTo(p));
            return;
        }
        while (1) {
            if (chi == p || isp(u, chi)) {
                break;
            }
            if (vis[chi]) {
                chi = vis[chi];
                continue;
            }
            cerr << "  " << u << ' ' << chi << '\n';
            assert(goTo(chi));
            self(self, chi, u);
        }
        if (p == -1) {
            p = chi;
            if (p == (1 << (MAXL / 2)) - 1) {
                return;
            }
            assert(goTo(p));
            self(self, p, -1);
        } else {
            assert(goTo(p));
        }
    };
    int tmp = get(0);
    if (tmp == 0) {
        REP (i, 1, n + 1) {
            if (i == start) continue;
            if (goTo(i)) {
                start = i;
                break;
            }
        }
    }
    dfs(dfs, start, -1);
    return;
}


/*
6
3 1
6 5
2 4
1 4
2 6
4
*/

Compilation message (stderr)

speedrun.cpp: In instantiation of 'assignHints(int, int, int*, int*)::<lambda(auto:23&&, int, int)> [with auto:23 = assignHints(int, int, int*, int*)::<lambda(auto:23&&, int, int)>&]':
speedrun.cpp:75:38:   required from here
speedrun.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   50 |         REP (i, 0, adj[u].size()) {
      |              ~~~~~~~~~~~~~~~~~~~        
speedrun.cpp:50:9: note: in expansion of macro 'REP'
   50 |         REP (i, 0, adj[u].size()) {
      |         ^~~
speedrun.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   63 |         REP (i, 0, adj[u].size()) {
      |              ~~~~~~~~~~~~~~~~~~~        
speedrun.cpp:63:9: note: in expansion of macro 'REP'
   63 |         REP (i, 0, adj[u].size()) {
      |         ^~~
speedrun.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (i + 1 < adj[u].size()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40