# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
335319 | 2020-12-12T00:13:12 Z | gmyu | Editor (BOI15_edi) | C++14 | 0 ms | 0 KB |
/* ID: USACO_template LANG: C++ PROG: USACO */ #include <iostream> //cin , cout #include <fstream> //fin, fout #include <stdio.h> // scanf , pringf #include <cstdio> #include <algorithm> // sort , stuff #include <stack> // stacks #include <queue> // queues #include <map> #include <string> using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; /// adjlist without weight typedef vector<pii> vii; /// adjlist with weight typedef vector<pair<int,pii>> vpip; /// edge with weight typedef long long ll; #define mp make_pair #define fst first #define snd second #define pb push_back #define sz(x) (int)(x).size() #define trav(u, adj_v) for (auto& u: adj_v) const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; // const ll INF = 1e18; // #define MAXV 300007 #define MAXE 100007 /// code from USACO examples void setIO(string name) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } bool debug = false, submit = true; int N; int a[MAXV], lev[MAXV]; #define MAXLCALOG 20 int anc[MAXV][MAXLCALOG]; int getP(int curr, int wantedDepth) { /// reach wanted depth if(lev[curr] <= wantedDepth) return curr; for(int k = MAXLCALOG - 1; k>= 0; k--) { while(anc[curr][k] > wantedDepth) { curr = anc[curr][k]; } } if(lev[curr] <= wantedDepth) return curr; return anc[curr][0]; } int main() { debug = true; submit = false; if(submit) setIO("Editor"); int i, j, k; cin >> N ; state[0] = 0; for(i=1; i <= N; i++) { cin >> a[i]; if(a[i] > 0) { lev[i] = 0; cout << a[i] << endl; } else { lev[i] = -a[i]; j = getP(i - 1, lev[i] - 1); k = getP(j - 1, lev[i] - 1); anc[i][0] = k; for(j = 1; j < MAXLCALOG; j++) anc[i][j] = anc[anc[i][j-1]][j-1]; k = getP(i, 0); cout << a[k] << endl; } } }