제출 #1243441

#제출 시각아이디문제언어결과실행 시간메모리
1243441thanhcodedaoBall Machine (BOI13_ballmachine)C++20
0 / 100
1097 ms22932 KiB
/****ThanhCodeDao*****/ /*******Azazel*******/ #include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define checkbit(mask,i) ((mask>>i)&1) #define bit(i) (1<<i) #define MLog 17 typedef long long ll; const ll maxN = 1e5+3, modd = 1e9+7; struct Point { ll x,y; }; ll cross(Point p,Point q,Point r) { // vi tri r voi duong pq >0 la ben trai, =0 la thang hang ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x); if(val < 0) return -1; if(val > 0) return 1; return 0; } ll dot(Point vecA,Point vecB) { // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc ll val = vecA.x*vecB.x + vecA.y*vecB.y; if(val < 0) return -1; if(val > 0) return 1; return 0; } double triarea(Point p,Point q,Point r) { // cross(pq * pr) / 2 double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x); return fabs(cross)/2.0; } int n,q,a[maxN],f[maxN],h[maxN],cv[maxN]; vector<int> adj[maxN]; int pa[MLog+1][maxN]; int root = 1; int st[maxN],fn[maxN],tour[2*maxN],cnt = 0; priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq; void pre_dfs(int u,int par) { st[u] = ++cnt; tour[cnt] = u; f[u] = a[u]; h[u] = h[par] + 1; for(int v : adj[u]) { if(v==par) continue; pre_dfs(v,u); f[u] = min(f[u],f[v]); } fn[u] = ++cnt; tour[cnt] = u; } struct Fenwick { vector<int> fen; Fenwick(int n) { fen.assign(n+3,0); } void up(int x,int delta) { for(; x<=cnt; x+=x&-x) { fen[x] += delta; } } int get(int x) { int res = 0; for(; x>=1; x-=x&-x) { res += fen[x]; } return res; } int getlr(int l,int r) { return get(r) - get(l-1); } }; bool cmp(int i,int j) { return f[i] < f[j]; } int times[maxN],curtime = 0; void dfs(int u,int par) { sort(adj[u].begin(),adj[u].end(),cmp); for(int v : adj[u]) { if(v==par) continue; dfs(v,u); } times[u] = ++curtime; pq.push({curtime,u}); } int kpar(int u,int k) { for(int i = MLog; i>=0; i--) { if(k>=bit(i)) { u = pa[i][u]; k -= bit(i); } } return u; } void solve() { cin >> n >> q; for(int i = 1; i<=n; i++) cin >> a[i]; for(int i = 1; i<=n; i++) { cin >> pa[0][i]; if(pa[0][i] == 0) { root = i; continue; } adj[i].pb(pa[0][i]); adj[pa[0][i]].pb(i); } pre_dfs(root,0); // eulertour, mang f for(int i = 1; i<=MLog; i++) { for(int j = 1; j<=n; j++) { pa[i][j] = pa[i-1][pa[i-1][j]]; } } dfs(root,0); Fenwick fen(cnt); while(q--) { int type,u; cin >> type >> u; int res = 0; if(type == 1) { while(u) { int v = pq.top().S; pq.pop(); --u; fen.up(st[v],1); fen.up(fn[v],-1); res = v; } } else { res = fen.getlr(st[root],st[u])-1; // tim cha cao nhat sao cho no get(1,cha) >= 1 int ans = kpar(u,res); fen.up(st[ans],-1); // day viec cho u bang cach xoa ans fen.up(fn[ans],+1); pq.push({times[ans],ans}); } cout << res << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); //freopen("inp.txt","r",stdin); //freopen("out.txt","w",stdout); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...