提出 9bf79f14-d880-4b57-ba04-2e73078108da

コード

#ifndef MAIN
#define MAIN
#include __FILE__

void _main()
{
	cint(n, q);
	vector<vector<xy>> dbl(31, vector<xy>(n, xy{0, inf}));
	vector<xyz> aq;
	rep(i, q)
	{
		cint(t, a, b);
		if (t == 1)
			dbl[0][a - 1] = xy{b - 1, i};
		else
			aq.push_back({a - 1, b, i});
	}
	rep(i, 30)
	{
		rep(j, n)
		{
			int nxt = dbl[i][j][0];
			dbl[i + 1][j] = xy{
				dbl[i][nxt][0], max(dbl[i][j][1], dbl[i][nxt][1])};
		}
	}
	for (auto [a, b, t] : aq)
	{
		if (n == 1)
		{
			cout << 1 << endl;
			continue;
		}
		xy val = xy{a, 0};
		repr(i, 31)
		{
			if (b & (1 << i))
			{
				val = xy{
					dbl[i][val[0]][0],
					max(val[1], dbl[i][val[0]][1]),
				};
			}
		}
		if (val[1] > t)
			cout << -1 << endl;
		else
			cout << val[0] + 1 << endl;
	}
}

#else

#ifdef DEBUG

#pragma GCC optimize("O0")

#else

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("trivial-auto-var-init=uninitialized")

#endif

#ifndef PRE_PROC
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <atcoder/all>
#endif
using namespace atcoder;
using modint10 = modint1000000007;
using modint9 = modint998244353;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<string> strvec;

constexpr ll mod10 = 1000000007;
constexpr ll mod9 = 998244353;

#define int ll
#define double ld
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repf(i, s, n) for (int i = s; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define reprt(i, e, n) for (int i = (int)(n) - 1; i >= e; i--)
#define rep2(i, j, n, m) rep(i, n) rep(j, m)
template <class... Args>
void __y_input(Args &...arg)
{

	(cin >> ... >> arg);
}

template <class... Args>
void __y_input_vec_1(int p, Args &...args)
{
	(cin >> ... >> args[p]);
}
template <class... Args>
void __y_input_vec_2(int p, int q, Args &...args)
{
	(cin >> ... >> args[p][q]);
}
template <class Arg>
void __y_input_vec_resize(int size, Arg &arg)
{
	arg.resize(size);
}
template <class Arg_t>
void __y_input_vec_resize_2(int n, int m, vector<Arg_t> &arg)
{
	arg.assign(n, Arg_t(m));
}
template <class... Args>
void __y_input_vec(int n, Args &...args)
{
	(__y_input_vec_resize(n, args), ...);
	rep(i, n)
	{
		(__y_input_vec_1(i, args), ...);
	}
}
template <class... Args>
void __y_input_vec2(int n, int m, Args &...args)
{
	(__y_input_vec_resize_2(n, m, args), ...);
	rep2(i, j, n, m)
	{
		(__y_input_vec_2(i, j, args), ...);
	}
}
template <class T, class... Args>
void SyncSort(vector<T> &vec, vector<Args> &...args)
{
	vector<pair<T, tuple<Args...>>> z;
	rep(i, vec.size())
	{
		z.push_back({vec[i], make_tuple(args.at(i)...)});
	}
	sort(z.begin(), z.end());
	rep(i, vec.size())
	{
		vec[i] = z[i].first;
		tie(args[i]...) = z[i].second;
	}
}

#define cint(...)    \
	int __VA_ARGS__; \
	__y_input(__VA_ARGS__)

#define cdbl(...)       \
	double __VA_ARGS__; \
	__y_input(__VA_ARGS__)

#define cstr(...)       \
	string __VA_ARGS__; \
	__y_input(__VA_ARGS__)

#define cit(t, ...) \
	t __VA_ARGS__;  \
	__y_input(__VA_ARGS__)

#define cvec(n, ...)         \
	vector<int> __VA_ARGS__; \
	__y_input_vec(n, __VA_ARGS__)

#define cvect(t, n, ...)   \
	vector<t> __VA_ARGS__; \
	__y_input_vec(n, __VA_ARGS__)

#define cvec2(n, m, ...)             \
	vector<vector<int>> __VA_ARGS__; \
	__y_input_vec2(n, m, __VA_ARGS__)

#define cvec2t(t, n, m, ...)       \
	vector<vector<t>> __VA_ARGS__; \
	__y_input_vec2(n, m, __VA_ARGS__)

#define cvecs(n, ...) cvect(string, n, __VA_ARGS__)

#define yn(bl) (bl ? "Yes" : "No")

#define all(v) v.begin(), v.end()

template <typename T>
using vec2 = vector<vector<T>>;
template <typename T>
using vec3 = vector<vector<vector<T>>>;

template <typename T>
constexpr T limit()
{
	return numeric_limits<long long>::max();
}

constexpr ll inf = limit<ll>() / 100;

template <typename T>
constexpr T limit(T _)
{
	return numeric_limits<long long>::max();
}

typedef array<int, 2> xy;
typedef array<int, 3> xyz;

template <typename T>
inline void sort(T &vec)
{
	return sort(vec.begin(), vec.end());
}
template <typename T>
inline void rsort(T &vec)
{
	return sort(vec.rbegin(), vec.rend());
}

template <typename T>
inline vector<vector<T>> rotate90(const vector<vector<T>> &vec)
{
	vector<vector<T>> res(vec[0].size(), vector<T>(vec.size()));
	rep(i, vec.size())
	{
		rep(j, vec[0].size())
		{
			res[j][vec.size() - i - 1] = vec[i][j];
		}
	}
	return res;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
	for (T val : vec)
	{
		os << val << ' ';
	}
	return os;
}

template <typename T>
vector<T> &operator+=(vector<T> &vec, const T &val)
{
	vec.push_back(val);
	return vec;
}

template <typename T>
vector<T> &operator+=(vector<T> &vec, const vector<T> &val)
{
	vec.insert(vec.end(), val.begin(), val.end());
	return vec;
}

template <typename T>
vector<T> &operator+=(vector<T> &vec, const initializer_list<T> &val)
{
	vec.insert(vec.end(), val.begin(), val.end());
	return vec;
}

template <typename T>
vector<vector<T>> operator*(vector<T> &vec, int val)
{
	return vector<vector<T>>(val, vec);
}

// Libraries Begin

map<int, int> prime_factorize(int n)
{
	map<int, int> res;
	for (int i = 2; i * i <= n; i += 1 + i > 2)
	{
		while (n % i == 0)
		{
			res[i]++;
			n /= i;
		}
	}
	if (n != 1)
	{
		res[n]++;
	}
	return res;
}

// Libraries End

// Defines

template <typename... T>
common_type_t<T...> __yc_max(T... args)
{
	return max(initializer_list<common_type_t<T...>>{args...});
}

template <typename... T>
common_type_t<T...> __yc_min(T... args)
{
	return min(initializer_list<common_type_t<T...>>{args...});
}

template <typename T>
vector<T> iota(size_t n, T start = 0)
{
	vector<T> res(n);
	iota(all(res), start);
	return res;
}

#define max(...) __yc_max(__VA_ARGS__)
#define min(...) __yc_min(__VA_ARGS__)

// Defines End

int isqrt(int x)
{
	int ok = 0, ng = 3037000500;
	while (ng - ok > 1)
	{
		int mid = (ok + ng) / 2;
		if (mid * mid <= x)
		{
			ok = mid;
		}
		else
		{
			ng = mid;
		}
	}
	return ok;
}

void _main();
signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	_main();
	return 0;
}

#endif

// 自分ここまでよくこのコード書いた！

//     __      ====^^====   //===\\       =======       ||=====\\     ||======    ||=====\| +
//    //\\         ||      //     \\     //      \\     ||      \|    ||          ||     || +
//   //  \\        ||      ||           ||        ||    ||      ||    ||======    ||=====// +
//  //====\\       ||      \\     //     \\      //     ||      /|    ||          || \\\    +
// //      \\      ||        \===//       \=====//      ||=====//     ||======    ||   \\\  +

結果

問題	点数	言語	結果	実行時間	メモリ
S. Association	0	C++ (gcc)	WA	1341 ms	30824 KiB

テストセット

テストセット	結果	実行時間	メモリ
testcase1	AC × 13 WA × 7	20 ms	8448 KiB
testcase2	AC × 9 WA × 3	893 ms	30812 KiB
testcase3	AC × 16 WA × 19	1341 ms	30824 KiB

詳細結果

テストケース	結果	実行時間	メモリ
sub1sub2sub3_hand_01.txt	AC	14 ms	8448 KiB
sub1sub2sub3_hand_02.txt	AC	14 ms	8192 KiB
sub1sub2sub3_hand_03.txt	AC	13 ms	8320 KiB
sub1sub2sub3_random_01.txt	AC	20 ms	8192 KiB
sub1sub2sub3_random_02.txt	AC	13 ms	8064 KiB
sub1sub2sub3_random_03.txt	AC	16 ms	8192 KiB
sub1sub3_corner_01.txt	AC	13 ms	8064 KiB
sub1sub3_corner_02.txt	WA	13 ms	8192 KiB
sub1sub3_corner_03.txt	WA	14 ms	8064 KiB
sub1sub3_corner_04.txt	AC	13 ms	8192 KiB
sub1sub3_corner_05.txt	WA	14 ms	8192 KiB
sub1sub3_corner_06.txt	WA	14 ms	8192 KiB
sub1sub3_corner_07.txt	WA	13 ms	8192 KiB
sub1sub3_example_01.txt	AC	15 ms	8192 KiB
sub1sub3_example_02.txt	AC	15 ms	8192 KiB
sub1sub3_hand_04.txt	AC	15 ms	8192 KiB
sub1sub3_hand_05.txt	AC	14 ms	8064 KiB
sub1sub3_random_04.txt	AC	13 ms	7936 KiB
sub1sub3_random_05.txt	WA	13 ms	8192 KiB
sub1sub3_random_06.txt	WA	15 ms	8448 KiB
sub2sub3_max_01.txt	WA	845 ms	30812 KiB
sub2sub3_max_02.txt	WA	802 ms	30556 KiB
sub2sub3_max_03.txt	WA	893 ms	30552 KiB
sub2sub3_random_07.txt	AC	334 ms	25564 KiB
sub2sub3_random_08.txt	AC	745 ms	18528 KiB
sub2sub3_random_09.txt	AC	465 ms	10296 KiB
sub3_corner_08.txt	WA	1205 ms	14320 KiB
sub3_corner_09.txt	WA	1341 ms	16760 KiB
sub3_corner_10.txt	WA	1205 ms	16892 KiB
sub3_max_04.txt	WA	794 ms	30676 KiB
sub3_max_05.txt	WA	817 ms	30656 KiB
sub3_max_06.txt	WA	811 ms	30680 KiB
sub3_random_10.txt	WA	495 ms	15760 KiB
sub3_random_11.txt	WA	514 ms	19152 KiB
sub3_random_12.txt	WA	514 ms	30824 KiB