QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #751543 | #5659. Watching Cowflix | _8_8_ | 8.333333 | 69ms | 25108kb | C++23 | 4.9kb | 2024-11-15 19:19:08 | 2024-11-15 19:19:08 |
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();
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 19976kb
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: 22116kb
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: 0
Wrong Answer
time: 46ms
memory: 25108kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...
output:
798 966 1070 1140 1199 1250 1293 1335 1375 1415 1454 1492 1529 1566 1603 1639 1674 1708 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 26...
result:
wrong answer 1st numbers differ - expected: '711', found: '798'
Test #4:
score: 0
Wrong Answer
time: 69ms
memory: 24836kb
input:
5000 0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...
output:
1126 1386 1493 1562 1622 1677 1727 1775 1821 1865 1908 1950 1989 2027 2064 2100 2136 2171 2206 2240 2273 2305 2336 2366 2395 2424 2452 2479 2506 2532 2557 2581 2604 2626 2648 2670 2691 2711 2730 2749 2768 2786 2804 2821 2837 2853 2869 2884 2898 2911 2923 2934 2944 2953 2962 2971 2980 2988 2995 3001 ...
result:
wrong answer 1st numbers differ - expected: '890', found: '1126'
Test #5:
score: 0
Wrong Answer
time: 56ms
memory: 23100kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...
output:
901 1121 1237 1315 1374 1424 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: '901'
Test #6:
score: 0
Wrong Answer
time: 4ms
memory: 15812kb
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: 17924kb
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: 0ms
memory: 15872kb
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: 4ms
memory: 15860kb
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: 2ms
memory: 17848kb
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: 0ms
memory: 15820kb
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: 2ms
memory: 17860kb
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: 0ms
memory: 15864kb
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: 0ms
memory: 17908kb
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: 0ms
memory: 15872kb
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: 15868kb
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: 3ms
memory: 18176kb
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: 15900kb
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: 15900kb
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: 17908kb
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: 4ms
memory: 17920kb
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: 0ms
memory: 17968kb
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: 4ms
memory: 15860kb
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: 16172kb
input:
200000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements