제출 #535393

#제출 시각아이디문제언어결과실행 시간메모리
535393KarabasanBall Machine (BOI13_ballmachine)C++17
100 / 100
149 ms46992 KiB
#include <bits/stdc++.h> #define ll long long #define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define endl "\n" #define int long long #define mod 1000000007 using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("fma,sse,sse2,sse3,avx") #pragma GCC optimize("unroll-loops") int n,q; int par[100005]; vector<int> v[100005]; int root; vector<int> dizi; int sub[100005]; vector<pair<int,int> > sira[100005]; int mark=0; int boya[100005]; int yer[100005]; int ata[100005][25]; int dfs(int x,int y) { sub[x]=x; if(v[x].size()==1&&x!=root) return sub[x]=x; for(auto i:v[x]) { if(i==y) continue; sira[x].push_back({dfs(i,x),i}); } sort(sira[x].begin(),sira[x].end()); for(int i=0;i<sira[x].size();i++) sub[x]=min(sub[x],sira[x][i].first); return sub[x]; } void dps(int x) { for(int i=0;i<sira[x].size();i++) dps(sira[x][i].second); dizi.push_back(x); yer[x]=dizi.size()-1; } void solve() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>ata[i][0]; if(ata[i][0]==0) { root=i; continue; } v[i].push_back(ata[i][0]); v[ata[i][0]].push_back(i); } dfs(root,0); dps(root); for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) ata[j][i]=ata[ata[j][i-1]][i-1]; while(q--) { int a,b; cin>>a>>b; if(a==1) { int c=0; int ind=0; while(c<b) { if(boya[dizi[ind]]==0) c++; boya[dizi[ind]]=1; ind++; } cout<<dizi[ind-1]<<endl; } else { int cvp=0; for(int i=20;i>=0;i--) { if(boya[ata[b][i]]==1) { b=ata[b][i]; cvp+=(1<<i); } } boya[b]=0; cout<<cvp<<endl; } } } signed main() { fast1 int t=1; //cin>>t; while(t--) { solve(); } return 0; }

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

ballmachine.cpp: In function 'long long int dfs(long long int, long long int)':
ballmachine.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<sira[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dps(long long int)':
ballmachine.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<sira[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...