#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<ll, ll> l4; typedef pair<double, double> dd; #define mp make_pair #define pb push_back #define mp3(a,b,c) mp(mp(a, b), c) #define debug(x) cerr << #x << " = " << x << " " typedef pair<double, double> dd; typedef pair<double, dd> d3; const double eps = 1e-9; const int N = 10000; const int M = 50; const int F = 10000 - 50; int h[N] = {0}; int maxi = 0; int cur = 0; int send_message(int N, int i, int Pi) { h[i] = h[Pi] + 1; bool _new = false; if (h[i] > h[maxi]) maxi = i, _new = true; if (i < F) return 0; if (i == F) { cur = maxi; } int msg = -1; if (_new) msg = 3; else if (cur <= 0) { msg = 2; } else { msg = cur&1; cur >>= 1; } return msg; } std::pair<int,int> longest_path(std::vector<int> S) { assert(S.size() == N); int i; for (i = N; i >= F && S[i] == 2; --i); if (S[i] == 3) return mp(0, i); int ret = 0; while (i >= F) { ret = ret * 2 + S[i]; --i; } return mp(0, ret); }