QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #751552 | #5659. Watching Cowflix | _8_8_ | 12.5 | 60ms | 24364kb | C++23 | 4.9kb | 2024-11-15 19:21:19 | 2024-11-15 19:21:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 1, MOD = (int)1e9 + 7;
int n, dp[N][2], up[N][20], tin[N], tout[N], timer, b = 20, par[N], w[N], dep[N];
bool ok[N];
set<int> g[N];
vector<pair<int, int>> e[N];
int root;
void build(int v, int pr) {
tin[v] = ++timer;
up[v][0] = pr;
for(int i = 1; i < b; i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:g[v]) {
if(to != pr) {
dep[to] = dep[v] + 1;
build(to, v);
}
}
tout[v] = ++timer;
}
bool is(int v, int u) {
return (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
int lca(int v, int u) {
if(is(v, u)) return v;
if(is(u, v)) return u;
for(int i = b - 1; i >= 0; i--) {
if(!is(up[v][i], u)) {
v = up[v][i];
}
}
return up[v][0];
}
bool cmp(int x, int y) {
return tin[x] < tin[y];
}
set<int> cur;
int p[N];
vector<int> er[N];
int get(int v) {
if(p[v] == v) return v;
int f = get(p[v]);
return p[v] = f;
}
void make() {
vector<int> t, t1;
for(int i = 1; i <= n; i++) {
if(ok[i]) {
t.push_back(i);
}
}
t1 = t;
sort(t.begin(), t.end(), cmp);
for(int i = 1; i < (int)t.size(); i++) {
t1.push_back(lca(t[i], t[i - 1]));
}
sort(t1.begin(), t1.end());
t1.resize(unique(t1.begin(), t1.end()) - t1.begin());
sort(t1.begin(), t1.end(), cmp);
vector<int> st;
for(int i:t1) {
cur.insert(i);
p[i] = i;
while(!st.empty() && !is(st.back(), i)) {
st.pop_back();
}
if(!st.empty()) {
e[st.back()].push_back({i, dep[i] - dep[st.back()] - 1});
par[i] = st.back();
w[i] = dep[i] - dep[st.back()] - 1;
}
st.push_back(i);
}
}
void prec() {
vector<int> u(n + 1), d(n + 1, 0);
function<void(int)> go = [&](int v){
d[v] = (ok[v] ? 0 : (int)1e9);
for(auto [to, w] : e[v]) {
go(to);
d[v] = min(d[to] + w + 1, d[v]);
}
};
function<void(int)> recalc = [&](int v) {
multiset<int> vals;
vals.insert(u[v]);
for(auto [to, w] : e[v]) {
vals.insert(d[to] + w);
}
for(auto [to, w] : e[v]) {
if(ok[to]) {
u[to] = 0;
recalc(to);
} else {
vals.erase(vals.find(d[to] + w));
u[to] = (*vals.begin()) + 1 + w;
vals.insert(d[to] + w);
}
}
};
go(root);
recalc(root);
for(int i:cur) if(!ok[i]) {
int mn = u[i] - 1, mn1 = (int)1e9;
for(auto [to, f] : e[i]) {
if(d[to] + f < mn) {
mn1 = mn;
mn = d[to] + f;
} else if(d[to] + f < mn1) {
mn1 = d[to] + f;
}
}
// if(mn == u[i] - 1 || mn1 == u[i] - 1) er[mn + mn1 + 1].push_back(i);
// else {
// assert(mn1 < u[i] - 1);
er[u[i] + mn].push_back(i);
// }
}
}
void remove(int i) {
p[i] = par[i];
cur.erase(i);
}
void solve(int v, int k) {
dp[v][1] = 1 + k;
for(auto [to, w] : e[v]) {
solve(to, k);
dp[v][0] += min(dp[to][0], dp[to][1]);
dp[v][1] += min(dp[to][0], min(dp[to][1], dp[to][1] + w - k));
}
if(ok[v]) {
dp[v][0] = (int)1e9;
}
}
void test() {
cin >> n;
if(n > 5000) return;
for(int i = 1; i <= n; i++) {
char x;cin >> x;
if(x == '1') {
ok[i] = 1;
root = i;
}
}
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].insert(v);
g[v].insert(u);
}
// root = 6;
build(root, root);
make();
prec();
for(int i = 1; i <= n; i++) {
e[i].clear();
}
int col = 0;
for(int k = 1; k <= n; k++) {
vector<int> rr;
for(int j:er[k]) {
remove(j);
col += w[j] + 1;
}
// for(int f:cur) if(f != root) {
// int t = get(par[f]);
// if(ok[f] && ok[t] && w[f] + 1 <= k) {
// rr.push_back(f);
// col += w[f] + 1;
// }
// }
for(int f : rr) {
remove(f);
}
for(int f:cur) {
if(f == root) continue;
int t = get(par[f]);
e[t].push_back({f, w[f]});
}
solve(root, k);
cout << min(dp[root][0], dp[root][1]) + col << '\n';
for(int f:cur) {
e[f].clear();
dp[f][0] = dp[f][1] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 24364kb
input:
5 10001 1 2 2 3 3 4 4 5
output:
4 6 8 9 10
result:
ok 5 number(s): "4 6 8 9 10"
Test #2:
score: 4.16667
Accepted
time: 0ms
memory: 20024kb
input:
7 0001010 7 4 5 6 7 2 5 1 6 3 2 5
output:
4 6 8 9 10 11 12
result:
ok 7 numbers
Test #3:
score: 4.16667
Accepted
time: 50ms
memory: 21068kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...
output:
711 837 944 1040 1121 1192 1249 1303 1352 1398 1439 1479 1518 1557 1596 1634 1671 1707 1742 1775 1807 1839 1871 1902 1932 1961 1990 2018 2046 2073 2099 2125 2150 2174 2197 2220 2242 2264 2286 2308 2329 2349 2368 2386 2404 2422 2439 2456 2472 2487 2502 2516 2529 2541 2552 2563 2573 2583 2593 2603 261...
result:
ok 5000 numbers
Test #4:
score: 0
Runtime Error
input:
5000 0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
Test #5:
score: 0
Wrong Answer
time: 60ms
memory: 20788kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...
output:
795 1025 1178 1284 1364 1422 1473 1517 1559 1600 1640 1679 1717 1754 1790 1826 1861 1895 1928 1960 1992 2024 2056 2088 2119 2150 2181 2211 2241 2270 2298 2325 2351 2376 2401 2425 2448 2471 2493 2515 2536 2556 2575 2594 2612 2629 2645 2660 2674 2688 2701 2713 2724 2734 2743 2751 2759 2766 2772 2777 2...
result:
wrong answer 1st numbers differ - expected: '794', found: '795'
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 15864kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 15912kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #8:
score: 0
Wrong Answer
time: 3ms
memory: 15916kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 18192kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #10:
score: 0
Wrong Answer
time: 4ms
memory: 17904kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 17848kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #12:
score: 0
Wrong Answer
time: 4ms
memory: 15860kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #13:
score: 0
Wrong Answer
time: 4ms
memory: 17968kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 4ms
memory: 16152kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 4ms
memory: 16156kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 15888kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 17912kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 15856kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 17852kb
input:
100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 17880kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #21:
score: 0
Wrong Answer
time: 0ms
memory: 15832kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #22:
score: 0
Wrong Answer
time: 3ms
memory: 17880kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 15856kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #24:
score: 0
Wrong Answer
time: 0ms
memory: 15860kb
input:
200000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements