QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#119796 | #5659. Watching Cowflix | pandapythoner# | 25 | 546ms | 40676kb | C++14 | 5.9kb | 2023-07-05 19:38:21 | 2024-07-04 00:19:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e18;
int n;
vector<int> s;
vector<vector<int>> g;
vector<ll> rs;
vector<int> usd;
vector<ll> dp_clrd, dp_not_clrd;
int dfs_usdc;
vector<int> dfs_usd;
vector<int> prnt;
void dfs0(int v, int p, ll k){
prnt[v] = p;
dfs_usd[v] = dfs_usdc;
dp_clrd[v] = -1 - k;
dp_not_clrd[v] = 0;
for(auto to: g[v]){
if(dfs_usd[to] != dfs_usdc && to != p && usd[to] == 0){
dfs0(to, v, k);
dp_not_clrd[v] += max(dp_clrd[to], dp_not_clrd[to]);
if(dp_clrd[to] + k > dp_not_clrd[to]){
dp_clrd[v] += dp_clrd[to] + k;
} else{
dp_clrd[v] += dp_not_clrd[to];
}
}
if(usd[to] == 2){
dp_clrd[v] += k;
}
}
}
void dfs1(int v, int p, ll k, bool clrd, ll &dsm, ll &dcmps){
if(clrd){
usd[v] = 1;
dsm += -1 - k;
dcmps -= 1;
for(auto to: g[v]){
if(to != p && usd[to] == 0){
if(dp_clrd[to] + k > dp_not_clrd[to]){
dcmps += 1;
dsm += k;
dfs1(to, v, k, true, dsm, dcmps);
} else{
dfs1(to, v, k, false, dsm, dcmps);
}
}
if(usd[to] == 2){
dsm += k;
dcmps += 1;
}
}
} else{
for(auto to: g[v]){
if(to != p && usd[to] == 0){
if(dp_clrd[to] > dp_not_clrd[to]){
dfs1(to, v, k, true, dsm, dcmps);
} else{
dfs1(to, v, k, false, dsm, dcmps);
}
}
}
}
}
void solve_slow(){
rs.resize(n + 1);
usd.resize(n);
for(int i = 0; i < n; i += 1){
if(s[i] == 0){
usd[i] = 0;
} else{
usd[i] = 2;
}
}
dfs_usdc = 10;
dfs_usd.assign(n, 0);
prnt.resize(n);
dp_clrd.resize(n);
dp_not_clrd.resize(n);
ll sm = 0;
ll components = 0;
for(int i = 0; i < n; i += 1){
if(s[i] == 1){
sm += 1;
components += 1;
}
}
for(int v = 0; v < n; v += 1){
for(auto to: g[v]){
if(v < to && usd[v] == 2 && usd[to] == 2){
components -= 1;
}
}
}
for(int k = 1; k <= n; k += 1){
dfs_usdc += 1;
sm += components;
vector<int> not_usd;
not_usd.reserve(n);
for(int i = 0; i < n; i += 1){
if(usd[i] == 0){
not_usd.push_back(i);
}
}
for(auto v: not_usd){
if(dfs_usd[v] != dfs_usdc){
dfs0(v, -1, k);
ll dsm = 0;
ll dcmps = 0;
if(dp_clrd[v] > dp_not_clrd[v]){
dfs1(v, -1, k, true, dsm, dcmps);
} else{
dfs1(v, -1, k, false, dsm, dcmps);
}
sm -= dsm;
components -= dcmps;
}
}
for(auto v: not_usd){
if(usd[v] == 1){
usd[v] = 2;
}
}
rs[k] = sm;
}
}
void solve(ll tl, ll tr, ll sm, ll cmps, vector<int> &vrtcs){
if(tl > tr){
return;
}
ll k = (tl + tr) / 2;
vector<int> lft_vrtcs, rght_vrtcs;
ll my_sm = sm + cmps * (k - tl + 1);
ll my_cmps = cmps;
dfs_usdc += 1;
for(auto v: vrtcs){
if(dfs_usd[v] != dfs_usdc){
dfs0(v, -1, k);
ll dsm = 0;
ll dcmps = 0;
if(dp_clrd[v] > dp_not_clrd[v]){
dfs1(v, -1, k, true, dsm, dcmps);
} else{
dfs1(v, -1, k, false, dsm, dcmps);
}
my_sm -= dsm;
my_cmps -= dcmps;
}
}
rs[k] = my_sm;
for(auto v: vrtcs){
if(usd[v] == 1){
lft_vrtcs.push_back(v);
} else{
rght_vrtcs.push_back(v);
}
}
solve(k + 1, tr, my_sm, my_cmps, rght_vrtcs);
for(auto v: rght_vrtcs){
usd[v] = 1;
}
for(auto v: lft_vrtcs){
usd[v] = 0;
}
solve(tl, k - 1, sm, cmps, lft_vrtcs);
}
void solve(){
rs.resize(n + 1);
usd.resize(n);
for(int i = 0; i < n; i += 1){
if(s[i] == 0){
usd[i] = 0;
} else{
usd[i] = 2;
}
}
dfs_usdc = 10;
dfs_usd.assign(n, 0);
prnt.resize(n);
dp_clrd.resize(n);
dp_not_clrd.resize(n);
ll sm = 0;
ll components = 0;
for(int i = 0; i < n; i += 1){
if(s[i] == 1){
sm += 1;
components += 1;
}
}
for(int v = 0; v < n; v += 1){
for(auto to: g[v]){
if(v < to && usd[v] == 2 && usd[to] == 2){
components -= 1;
}
}
}
vector<int> vrtcs;
for(int i = 0; i < n; i += 1){
if(usd[i] == 0){
vrtcs.push_back(i);
}
}
solve(1, n, sm, components, vrtcs);
}
int32_t main(){
if(1){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
// assert(n <= 1e4);
s.resize(n);
for(int i = 0; i < n; i += 1){
char c;
cin >> c;
s[i] = c - '0';
}
g.assign(n, vector<int>());
for(int i = 0; i < n - 1; i += 1){
int u, v;
cin >> u >> v;
--u;
--v;
g[u].push_back(v);
g[v].push_back(u);
}
solve();
for(int k = 1; k <= n; k += 1){
cout << rs[k] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 3668kb
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: 3564kb
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: 3ms
memory: 4316kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...
output:
711 837 957 1040 1124 1203 1277 1349 1352 1401 1449 1496 1541 1586 1631 1675 1718 1760 1742 1776 1809 1842 1875 1907 1938 1968 1998 2027 2056 2084 2111 2138 2164 2189 2213 2237 2260 2283 2286 2308 2329 2349 2368 2386 2404 2422 2439 2456 2472 2487 2502 2516 2529 2541 2552 2563 2573 2583 2593 2603 261...
result:
wrong answer 3rd numbers differ - expected: '944', found: '957'
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 4500kb
input:
5000 0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...
output:
890 1226 1472 1547 1649 1748 1845 1940 1821 1866 1910 1953 1995 2036 2076 2115 2154 2192 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 3...
result:
wrong answer 3rd numbers differ - expected: '1433', found: '1472'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 4240kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...
output:
794 1025 1199 1284 1382 1475 1561 1641 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 3rd numbers differ - expected: '1178', found: '1199'
Test #6:
score: 4.16667
Accepted
time: 148ms
memory: 32012kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30804 41189 48182 51855 52223 52591 52958 53324 53690 54055 54419 54782 55144 55505 55865 56224 56582 56939 57295 57650 58004 58357 58709 59061 59412 59762 60111 60459 60806 61152 61497 61841 62184 62526 62867 63207 63546 63884 64222 64559 64895 65230 65564 65898 66231 66563 66894 67224 67554 67883 ...
result:
ok 200000 numbers
Test #7:
score: 4.16667
Accepted
time: 144ms
memory: 32248kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30644 41023 48123 51892 52268 52643 53017 53390 53763 54135 54506 54876 55245 55613 55980 56346 56712 57077 57441 57804 58166 58528 58889 59249 59608 59966 60323 60679 61034 61388 61741 62093 62445 62796 63146 63495 63843 64190 64536 64881 65225 65568 65910 66251 66591 66931 67270 67608 67945 68281 ...
result:
ok 200000 numbers
Test #8:
score: 4.16667
Accepted
time: 132ms
memory: 31996kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30736 41111 48167 51868 52239 52609 52978 53346 53714 54081 54447 54812 55176 55539 55902 56264 56625 56985 57344 57702 58060 58417 58774 59130 59485 59839 60192 60544 60895 61245 61594 61942 62289 62635 62980 63324 63668 64011 64353 64695 65036 65377 65717 66057 66396 66734 67071 67408 67744 68079 ...
result:
ok 200000 numbers
Test #9:
score: 0
Wrong Answer
time: 65ms
memory: 16532kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12231 15712 15163 16300 17331 17762 18418 19056 19668 20270 20860 20243 20535 20827 21118 21409 21699 21989 22277 22564 22850 23136 23420 22900 23090 23279 23467 23655 23842 24028 24213 24398 24582 24765 24948 25131 25313 25495 25676 25856 26036 26215 26393 26571 26748 26925 27102 27029 27192 27355 ...
result:
wrong answer 2nd numbers differ - expected: '13861', found: '15712'
Test #10:
score: 0
Wrong Answer
time: 93ms
memory: 17072kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15993 21937 25281 27931 30360 28313 28818 29322 29823 30323 30822 29846 30047 30247 30446 30645 30844 31042 31239 31436 31633 31829 32024 32099 32281 32462 32642 32821 33000 33178 33355 33531 33706 33880 34053 34225 34396 34566 34735 34904 35073 35242 35410 35578 35745 35912 36078 36243 36408 36573 ...
result:
wrong answer 2nd numbers differ - expected: '21877', found: '21937'
Test #11:
score: 0
Wrong Answer
time: 106ms
memory: 16768kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14608 18567 21252 23670 25846 24472 24916 25358 25796 26233 26666 25807 25993 26179 26365 26550 26735 26920 27104 27288 27472 27656 27839 28010 28191 28372 28552 28732 28912 29091 29269 29447 29624 29801 29977 30152 30327 30502 30677 30851 31024 31196 31368 31539 31710 31881 32051 32220 32388 32556 ...
result:
wrong answer 2nd numbers differ - expected: '18481', found: '18567'
Test #12:
score: 0
Wrong Answer
time: 69ms
memory: 17300kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12198 15655 15093 16220 17244 17738 18418 19082 19731 20375 21007 20361 20691 21020 21348 21675 22001 22325 22649 22972 23293 23613 23932 23363 23585 23806 24026 24246 24465 24683 24901 25119 25336 25553 25769 25984 26198 26412 26625 26838 27051 27264 27477 27689 27900 28111 28321 28251 28445 28639 ...
result:
wrong answer 2nd numbers differ - expected: '13815', found: '15655'
Test #13:
score: 0
Wrong Answer
time: 91ms
memory: 17024kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16072 22021 25331 27983 30406 28439 28947 29453 29957 30460 30959 30031 30237 30442 30646 30850 31054 31257 31460 31662 31863 32063 32262 32343 32530 32716 32902 33087 33271 33455 33638 33820 34001 34181 34361 34540 34718 34895 35071 35246 35421 35595 35769 35943 36117 36290 36462 36633 36803 36972 ...
result:
wrong answer 2nd numbers differ - expected: '21956', found: '22021'
Test #14:
score: 0
Wrong Answer
time: 93ms
memory: 16684kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14721 18772 21526 24003 26239 25022 25543 26060 26576 27091 27604 26556 26770 26984 27197 27409 27620 27831 28041 28250 28458 28666 28873 29068 29273 29477 29680 29882 30083 30283 30482 30680 30877 31073 31269 31465 31661 31856 32050 32243 32436 32628 32819 33010 33200 33390 33579 33767 33954 34141 ...
result:
wrong answer 2nd numbers differ - expected: '18698', found: '18772'
Test #15:
score: 0
Wrong Answer
time: 72ms
memory: 16552kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12121 15560 15063 16211 17253 17644 18303 18939 19559 20171 20777 20159 20466 20771 21076 21380 21682 21983 22282 22580 22877 23173 23468 22881 23076 23270 23464 23657 23850 24042 24233 24423 24612 24801 24990 25179 25367 25554 25740 25925 26109 26292 26475 26658 26840 27021 27202 27104 27271 27437 ...
result:
wrong answer 2nd numbers differ - expected: '13753', found: '15560'
Test #16:
score: 0
Wrong Answer
time: 97ms
memory: 17072kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16192 22165 25455 28069 30465 28532 29039 29545 30049 30548 31046 30066 30267 30468 30668 30867 31065 31263 31461 31659 31856 32052 32247 32316 32497 32677 32856 33034 33212 33389 33566 33743 33920 34096 34272 34447 34621 34794 34966 35137 35308 35479 35649 35818 35986 36153 36319 36484 36648 36811 ...
result:
wrong answer 2nd numbers differ - expected: '22112', found: '22165'
Test #17:
score: 0
Wrong Answer
time: 104ms
memory: 16808kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14705 18734 21466 23893 26084 24932 25456 25978 26498 27009 27508 26586 26827 27067 27307 27546 27785 28023 28260 28496 28731 28966 29200 29433 29666 29898 30129 30359 30589 30818 31047 31275 31502 31728 31953 32177 32401 32624 32846 33067 33287 33507 33726 33945 34163 34381 34598 34814 35029 35243 ...
result:
wrong answer 2nd numbers differ - expected: '18667', found: '18734'
Test #18:
score: 0
Wrong Answer
time: 73ms
memory: 16584kb
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12282 15668 15142 16281 17293 17756 18416 19063 19694 20306 20907 20273 20577 20880 21181 21482 21782 22081 22379 22676 22972 23267 23562 22938 23131 23323 23514 23704 23893 24082 24270 24457 24643 24829 25014 25198 25381 25563 25745 25927 26109 26290 26470 26649 26827 27004 27180 27116 27279 27441 ...
result:
wrong answer 2nd numbers differ - expected: '13869', found: '15668'
Test #19:
score: 4.16667
Accepted
time: 165ms
memory: 19088kb
input:
100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 25...
result:
ok 100000 numbers
Test #20:
score: 0
Wrong Answer
time: 203ms
memory: 31172kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
32208 43929 50276 55340 59958 56024 56926 57826 58719 59610 60498 58476 58768 59059 59350 59640 59930 60220 60510 60800 61090 61379 61667 61691 61953 62214 62474 62733 62991 63248 63504 63759 64013 64267 64520 64772 65023 65273 65522 65771 66019 66266 66513 66760 67006 67251 67495 67738 67980 68221 ...
result:
wrong answer 2nd numbers differ - expected: '43788', found: '43929'
Test #21:
score: 0
Wrong Answer
time: 235ms
memory: 30528kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
29187 37186 42486 47196 51413 48729 49593 50453 51303 52144 52979 50856 51133 51409 51684 51959 52233 52506 52779 53052 53325 53597 53869 54119 54389 54659 54928 55197 55465 55732 55998 56263 56528 56792 57055 57317 57579 57841 58103 58364 58624 58884 59143 59401 59658 59915 60171 60426 60681 60936 ...
result:
wrong answer 2nd numbers differ - expected: '37057', found: '37186'
Test #22:
score: 0
Wrong Answer
time: 162ms
memory: 32152kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
24124 30874 29594 31671 33553 34385 35586 36758 37888 38997 40095 38868 39367 39866 40364 40861 41358 41854 42348 42842 43335 43827 44318 43101 43392 43683 43973 44262 44550 44837 45124 45410 45695 45979 46263 46546 46829 47111 47393 47674 47955 48235 48514 48793 49071 49349 49626 49478 49734 49989 ...
result:
wrong answer 2nd numbers differ - expected: '27220', found: '30874'
Test #23:
score: 0
Wrong Answer
time: 215ms
memory: 31076kb
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
32229 44105 50557 55650 60343 56305 57185 58062 58934 59802 60667 58701 58996 59290 59583 59876 60169 60462 60755 61047 61338 61628 61917 61927 62191 62455 62718 62980 63242 63503 63764 64024 64283 64542 64800 65057 65314 65570 65826 66081 66335 66588 66840 67091 67341 67590 67838 68085 68332 68578 ...
result:
wrong answer 2nd numbers differ - expected: '44001', found: '44105'
Test #24:
score: 0
Wrong Answer
time: 546ms
memory: 40676kb
input:
200000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 25...
result:
wrong answer 18425th numbers differ - expected: '43404', found: '43405'