| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094357 | Sunbae | 9월 (APIO24_september) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
asser(cnt > = 0 && cnt < n);
return cnt;
}