Code Festival Team Relay B - Evergrowing Tree
問題ページ B - Evergrowing Tree
考えたこと
- 同じ頂点にたどり着くまで上にたどっていけばよさそう
- 完全N分木なのでダブリングしなくても上にたどるのは対数オーダー
- 根を0とすると頂点vの親は(v-1)/Nになる
- vとwの深さをそろえた後頂点が一致するまでたどっていけばO(Qlog(max(v,w)))でできそうだったので出すとTLE(????)
- バグって無限ループなのかとか探し続けたがN=1がコーナーケースでたどる部分が線形オーダーになるのでTLEになる
コーナーケースには気をつけよう…
#include <bits/stdc++.h> using namespace std; typedef long long ll; // #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int w[100010], v[100010]; signed main(void) { int n, q; scanf("%d %d", &n, &q); REP(i, q) { scanf("%d %d", &v[i], &w[i]); v[i]--, w[i]--; } REP(i, q) { if(n == 1) { printf("%d\n", v[i]+1); continue; } int d_v = 0, vv = v[i]; while(vv > 0) vv = (vv-1)/n, d_v++; int d_w = 0, ww = w[i]; while(ww > 0) ww = (ww-1)/n, d_w++; if(d_v < d_w) { REP(j, d_w-d_v) { w[i] = (w[i]-1)/n; } } else if(d_w < d_v) { REP(j, d_v-d_w) { v[i] = (v[i]-1)/n; } } while(w[i] != v[i]) { w[i] = (w[i]-1)/n; v[i] = (v[i]-1)/n; } printf("%d\n", w[i]+1); } return 0; }