제출 #195590

#제출 시각아이디문제언어결과실행 시간메모리
195590karmaBall Machine (BOI13_ballmachine)C++14
20.95 / 100
927 ms21944 KiB
#include <bits/stdc++.h> #define pb emplace_back #define ll long long #define fi first #define se second #define mp make_pair //#define int int64_t using namespace std; const int N = (int)1e5 + 2; const int logN = 20; int p[N][logN + 1], del[N], d[N], deg[N]; int root, n, q, x, k, low, high, mid; vector<int> a[N]; set<int> leaf; void DFS(int u) { deg[u] = a[u].size(); for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1]; if(!deg[u]) leaf.insert(u); for(int v: a[u]) d[v] = d[u] + 1, DFS(v); } int Node(int x, int step) { for(int i = logN; i >= 0; --i) if(step >= (1 << i)) x = p[x][i], step -= (1 << i); return x; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); #define Task "test" if(fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n >> q; for(int i = 1; i <= n; ++i) { cin >> p[i][0]; a[p[i][0]].pb(i); if(!p[i][0]) root = i; } DFS(root); while(q --) { cin >> x >> k; if(x == 1) { while(k --) { x = *leaf.begin(); leaf.erase(x); if(--deg[p[x][0]] == 0) leaf.insert(p[x][0]); del[x] = 1; } cout << x << '\n'; } else { low = 0, high = d[k]; while(low <= high) { mid = (low + high) >> 1; if(del[Node(k, mid)]) low = mid + 1; else high = mid - 1; } x = Node(k, high), del[x] = 0, leaf.insert(x); if(++deg[p[x][0]] == 1) leaf.erase(p[x][0]); cout << d[k] - d[x] << '\n'; } } }

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...