QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523533 | #7118. Closing Time | kimmoqt | 9 | 2ms | 8244kb | C++20 | 3.5kb | 2024-08-18 13:21:14 | 2024-08-18 13:21:18 |
answer
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
int par[MX];
ll A[MX],B[MX];
vector<pair<int,int>> adj[MX];
bool vis[MX], calc[MX], inPath[MX];
void dfs(int v, int p) {
par[v]=p;
for(auto [u,w]:adj[v]) {
if(u==p) continue;
A[u]=A[v]+w;
dfs(u,v);
}
}
void dfs2(int v, int p) {
for(auto [u,w]:adj[v]) {
if(u==p) continue;
B[u]=B[v]+w;
dfs2(u,v);
}
}
// called multiple times
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
for(int i=0;i<N;i++) {
adj[i].clear();
vis[i]=calc[i]=false;
par[i]=-1;
A[i]=B[i]=0;
}
for(int i=0;i<N-1;i++) {
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
}
dfs(X,-1);
dfs2(Y,-1);
priority_queue<pair<ll,ll>> pq;
int v=Y;
vector<int> path;
while(v!=X) {
inPath[v]=true;
path.push_back(v);
v=par[v];
}
inPath[X]=true;
path.push_back(X);
v=Y;
while(v!=X) {
if(A[par[v]]<B[par[v]]) {
pq.push({-abs(A[par[v]]-B[par[v]]),par[v]});
pq.push({-abs(A[v]-B[v]),v});
vis[par[v]]=true;
vis[v]=true;
break;
}
v=par[v];
}
int ans=0,cnt=0;
ll sum=0;
for(auto x:path) {
sum+=min(A[x],B[x]);
calc[x]=true;
cnt++;
}
{
vector<ll> vals;
for(int i=0;i<N;i++) vals.push_back(min(A[i],B[i]));
sort(vals.begin(),vals.end());
ll cur=0;
for(int i=0;i<N;i++) {
cur+=vals[i];
if(cur<=K) ans=max(ans,i+1);
}
}
while(!pq.empty()) {
auto [d,v]=pq.top(); pq.pop();
d=-d;
calc[v]=true;
cnt+=1+!inPath[v];
sum+=d;
ll cur=sum;
vector<int> del;
vector<pair<ll,ll>> vals;
for(int i=0;i<N;i++) {
if(!calc[i]) vals.push_back({min(A[i],B[i]),i});
}
sort(vals.begin(),vals.end());
for(int i=0;i<vals.size();i++) {
if(cur+vals[i].first>K) break;
cur+=vals[i].first;
cnt++;
del.push_back(vals[i].second);
}
if(cur<=K) ans=max(ans,cnt);
for(auto [u,w]:adj[v]) {
if(!vis[u]) {
vis[u]=true;
if(inPath[u]) pq.push({-abs(A[u]-B[u]),u});
else pq.push({-max(A[u],B[u]),u});
}
}
for(auto x:del) {
calc[x]=false;
cnt--;
}
}
return ans;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 31011 61157 8517583098 31011 129396 964383 1655 129396 331139 1655 191487 566483 110385 191487 865248 43212 110385 542661 43212 81682 13766 81682 91774 546589 91774 124706 780638 124706 175650 118706 10421 175650 615314 10421 151953 436270 140430 151...
output:
result:
Subtask #2:
score: 9
Accepted
Test #4:
score: 9
Accepted
time: 2ms
memory: 7944kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 23 25 382806473 0 1 375710 1 2 898637 2 3 10402 3 4 536577 4 5 385023 5 6 71075 6 7 543368 7 8 301497 8 9 174394 9 10 711312 10 11 923006 11 12 675532 12 13 838667 13 14 565729 14 15 979816 15 16 862618 16 17 576015 17 18 177751 18 19 306989 19 20 881492...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 96
result:
ok
Test #5:
score: 9
Accepted
time: 1ms
memory: 8244kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 47 20 22 25669694 0 1 291237 1 2 851987 2 3 421247 3 4 962919 4 5 643085 5 6 224951 6 7 756890 7 8 147295 8 9 625823 9 10 736374 10 11 290526 11 12 335466 12 13 539086 13 14 957449 14 15 423408 15 16 932444 16 17 356032 17 18 307118 18 19 94279 19 20 989546...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 26
result:
ok
Test #6:
score: 9
Accepted
time: 1ms
memory: 7980kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 46 6 34 355277954 0 1 574359 1 2 58362 2 3 778155 3 4 538832 4 5 128903 5 6 79774 6 7 715282 7 8 259924 8 9 640303 9 10 361135 10 11 506866 11 12 527045 12 13 946672 13 14 620381 14 15 701743 15 16 766266 16 17 524732 17 18 340089 18 19 630172 19 20 357712 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 74
result:
ok
Test #7:
score: 9
Accepted
time: 0ms
memory: 8232kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 45 14 44 70669 0 1 266130 1 2 372315 2 3 965349 3 4 119493 4 5 190522 5 6 506822 6 7 45330 7 8 423189 8 9 748532 9 10 653554 10 11 102552 11 12 90431 12 13 843259 13 14 422626 14 15 35334 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 4
result:
ok
Test #8:
score: 9
Accepted
time: 1ms
memory: 7948kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 0 49 332340134 0 1 987193 1 2 950856 2 3 893737 3 4 870689 4 5 810192 5 6 790242 6 7 744052 7 8 714922 8 9 677074 9 10 630082 10 11 599644 11 12 528415 12 13 491648 13 14 479486 14 15 439182 15 16 371085 16 17 357776 17 18 308161 18 19 254481 19 20 20430...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 44
result:
ok
Test #9:
score: 9
Accepted
time: 1ms
memory: 8240kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 0 49 329827838 0 1 972981 1 2 953594 2 3 908629 3 4 849675 4 5 808354 5 6 782643 6 7 759387 7 8 698618 8 9 650896 9 10 639153 10 11 591828 11 12 532588 12 13 503214 13 14 447660 14 15 403224 15 16 380834 16 17 327127 17 18 300115 18 19 244025 19 20 23362...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 44
result:
ok
Test #10:
score: 9
Accepted
time: 1ms
memory: 7940kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 3 0 1 1 0 1 1 1 2 1
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 3
result:
ok
Test #11:
score: 9
Accepted
time: 1ms
memory: 7936kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 8 9 31897732 0 1 428932 1 2 103619 2 3 805647 3 4 691922 4 5 320369 5 6 755877 6 7 701672 7 8 426711 8 9 507102 9 10 492732 10 11 68466 11 12 317311 12 13 37666 13 14 499673 14 15 502226 15 16 753200 16 17 523387 17 18 904778 18 19 695859
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 30
result:
ok
Test #12:
score: 9
Accepted
time: 1ms
memory: 7948kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 15 16 25160185 0 1 193268 1 2 139314 2 3 193167 3 4 446469 4 5 793626 5 6 502774 6 7 598587 7 8 69975 8 9 499282 9 10 943594 10 11 804459 11 12 536095 12 13 578060 13 14 142523 14 15 364845 15 16 181397 16 17 64327 17 18 224827 18 19 439557
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 26
result:
ok
Test #13:
score: 9
Accepted
time: 0ms
memory: 8016kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 0 19 77846543 0 1 603320 1 2 433257 2 3 572719 3 4 340716 4 5 549198 5 6 383420 6 7 50703 7 8 720210 8 9 304217 9 10 162280 10 11 68594 11 12 401595 12 13 446738 13 14 920882 14 15 494739 15 16 616729 16 17 874820 17 18 269830 18 19 53532
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 34
result:
ok
Test #14:
score: 9
Accepted
time: 1ms
memory: 8240kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 19 2 17 6692 0 1 748749 1 2 369010 2 3 3351 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 3346 17 18 11355
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 3
result:
ok
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 7916kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 25 20 9 16 34385 0 1 196 1 2 733 2 3 758 3 4 92 4 5 636 5 6 462 6 7 491 7 8 239 8 9 873 9 10 983 10 11 72 11 12 988 12 13 690 13 14 162 14 15 287 15 16 247 16 17 121 17 18 140 18 19 64 20 9 13 37109 0 1 530 1 2 588 2 3 841 3 4 274 4 5 994 5 6 879 6 7 879 7 8 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 25 23 31 30 30 29 25 29 26 23 26 26 28 22 26 23 23 26 25 23 25 25 23 24 29
result:
wrong answer 2nd lines differ - on the 1st token, expected: '25', found: '23'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 1ms
memory: 7904kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 9 0 2 2 1 2 3 2 3 3
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 5
result:
wrong answer 1st lines differ - on the 1st token, expected: '6', found: '5'
Subtask #6:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #4:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%