제출 #1094356

#제출 시각아이디문제언어결과실행 시간메모리
1094356Sunbae9월 (APIO24_september)C++17
0 / 100
6 ms3676 KiB
#include <cstdio> #include <algorithm> #include <vector> #include "september.h" using namespace std; const int N = 1e5 + 5, M = 2e5 + 20; vector<int> g[N]; int bit[M], tin[N], tout[N], mn[N], mx[N], ti; void upd(int i, int v){ for(; i<M; i+=i&-i) bit[i] += v;} int qry(int i){ int r = 0; for(; i; i-=i&-i) r += bit[i]; return r;} void dfs(int u){ tin[u] = ti++; for(int v: g[u]) dfs(v); tout[u] = ti-1; } int solve(int n, int m, vector<int> up, vector<vector<int>> S){ for(int i = 0; i<n; ++i) g[i].clear(); for(int i = ti = 1; i<n; ++i) g[up[i]].push_back(i); dfs(0); fill(mn, mn+n, n+1); fill(mx, mx+n, 0); for(int i = 0, cnt; i<m; ++i){ fill(bit, bit+n+1, cnt = 0); for(int u: S[i]){ if(!qry(tin[u])){ ++cnt; upd(tin[u], +cnt); upd(tout[u]+1, -cnt); } } for(int j = 1; j<n; ++j){ int tmp = qry(tin[j]); mn[j] = min(mn[j], tmp); mx[j] = max(mx[j], tmp); } } fill(bit, bit+(n<<1)+20, 0); int MN = (n<<1) + 20, MX = 0; for(int i = 1; i<n; ++i){ int l = (mn[i]<<1), r = (mx[i]<<1); upd(l, +1); upd(r+1, -1); MN = min(MN, l); MX = max(MX, r); } int cnt = 0; for(int i = MN; i<=MX; ++i) if(qry(i) && !qry(i-1)) ++cnt; return cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...