제출 #145517

#제출 시각아이디문제언어결과실행 시간메모리
145517miguelBall Machine (BOI13_ballmachine)C++14
91.43 / 100
1061 ms33164 KiB
/* ░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░ ░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░ ░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░ ░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░ ░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░ ░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░ ░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░ ░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░ ░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░ ░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░ ░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░ ░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░ ░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██ ░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█ ░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀ ░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░ ░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░ █▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░ █░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░*/ # pragma GCC optimize("Ofast") # pragma GCC optimization ("unroll-loops") #include<bits/stdc++.h> using namespace std; #define pb push_back #define dbg(x) cout << #x << '=' << x << '\n'; #define ll long long #define x first #define y second #define pi pair <int, int> #define vi vector <int> const ll mod = 1000000007; const ll nmax=100010; #define int ll int p[100010][18], n, q, root, subtree[100010], id[100010], cnt=1; vi g[100010]; set<pi> s; int dfs(int nod){ int mn=1e9; for(int i: g[nod]){ mn=min(dfs(i), mn); } subtree[nod]=min(mn, nod); return subtree[nod]; } void dfs_id(int nod){ for(int i: g[nod]){ dfs_id(i); } id[nod]=cnt; cnt++; } void dfs_p(int nod){ for(int i=1; i<=17; i++) p[nod][i]=p[p[nod][i-1]][i-1]; for(int i: g[nod]) dfs_p(i); } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cin>>n>>q; for(int i=1; i<=n; i++){ cin>>p[i][0]; g[p[i][0]].pb(i); if(p[i][0]==0) root=i; } dfs(root); for(int i=1; i<=n; i++){ if(g[i].size()) sort(g[i].begin(), g[i].end(), [](int a, int b){return (subtree[a]<subtree[b]);}); } //id-s(order) and parents by lifting ye boi dfs_id(root); s.insert({(ll)1e9, 0LL}); for(int i=1; i<=n; i++) s.insert({id[i], i}); dfs_p(root); while(q--){ int op, x; cin>>op>>x; if(op==1){ for(int cnt=1; cnt<=x; cnt++){ if(cnt==x) cout<<(*s.begin()).y<<"\n"; s.erase(s.begin()); } } else if(op==2){ int cur=x, ans=0; for(int i=17; i>=0; i--){ int nod=p[cur][i]; if(nod!=0 && (s.size()==0 || s.find(make_pair(id[nod], nod))==s.end())) cur=nod, ans+=(nod!=0)*(1<<i); } cout<<ans<<"\n"; s.insert({id[cur], cur}); //for(pi i : s) cout<<i.y<<" "; cout<<endl; } } }

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

ballmachine.cpp:22:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...