QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#154186 | #7118. Closing Time | paul2008 | 8 | 119ms | 79336kb | C++14 | 4.5kb | 2023-08-31 14:37:25 | 2023-08-31 14:37:26 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const long long N=4e5+5;
vector <long long> g[N],w[N];
long long fat[N],fa[N],son[N],a[N],n;
long long distx[N],disty[N];
bool inpath[N];
void dfsx(long long x,long long fa)
{
for(long long i=0;i<g[x].size();i++)
{
long long to=g[x][i];
if(to==fa)
continue;
fat[to]=x;
distx[to]=distx[x]+w[x][i];
dfsx(to,x);
}
}
void dfsy(long long x,long long fa)
{
for(long long i=0;i<g[x].size();i++)
{
long long to=g[x][i];
if(to==fa)
continue;
disty[to]=disty[x]+w[x][i];
dfsy(to,x);
}
}
long long calc(long long k)
{
priority_queue <long long,vector <long long>,greater<long long> > q;
for(long long i=1;i<=n;i++)
q.push(distx[i]);
for(long long i=1;i<=n;i++)
q.push(disty[i]);
long long ans=0;
while(!q.empty())
{
long long x=q.top();
q.pop();
k -= x, ans++;
if(k<0)
return ans-1;
}
return ans;
}
void add(long long x,long long y,long long z)
{
g[x].push_back(y);
w[x].push_back(z);
}
struct node
{
long long sz,sum;
long long id;
bool operator <(const node& oth) const
{
return sum*oth.sz>oth.sum*sz;
}
}val[N];
bool del[N],in[N];
pair <long long,long long> edge[N];
long long sumfirst[N];
long long cnt;
priority_queue <pair<long long,long long>,vector <pair<long long,long long> >,greater<pair<long long,long long> > > q;
long long gettop()
{
while(del[q.top().second])
q.pop();
in[q.top().second]=true;
long long ans=q.top().first;
q.pop();
return ans;
}
bool check(long long m,long long k) //判断是否可以取m个,上界为k
{
if(m==cnt*2+1)
return false;
while(!q.empty())
q.pop();
for(long long i=1;i<=cnt*2;i++)
del[i]=in[i]=false;
sort(edge+1,edge+cnt+1);
for(long long i=1;i<=cnt;i++) //处理第一行的前缀和
sumfirst[i]=sumfirst[i-1]+edge[i].second;
for(long long i=1;i<=cnt;i++)
q.push(make_pair(edge[i].first-edge[i].second,i+cnt)); //第一行的标号为i,第二行的标号为i+cnt
long long nowsum=0;
for(long long i=1;i<=m-cnt;i++)
nowsum += gettop();
for(long long i=cnt;i>=0;i--) //[1,i]都取了第一行,这些列的决策都为“第二行”,[i+1,n]都不能取第二行,决策为“第一行”
{ //要维护前m-i小的和
if(i>m)
continue;
if(nowsum+sumfirst[i]<=k) //当前这个i是合法的
return true;
if(i+cnt<=m)
return false;
//更新nowsum
q.push(make_pair(edge[i].second,i));
nowsum += gettop();
del[i+cnt]=true;
if(in[i+cnt])
{
in[i+cnt]=false;
nowsum -= edge[i].first-edge[i].second;
nowsum += gettop();
}
}
return false;
}
void add(long long x,long long y)
{
edge[++cnt]=make_pair(x+y,x);
}
int max_score(int N, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W)
{
n=N, x++, y++, cnt=0;
for(long long i=1;i<=n;i++)
g[i].clear(), w[i].clear(), inpath[i]=false, distx[i]=disty[i]=fat[i]=0;
for(long long i=0;i<n-1;i++)
{
add(U[i]+1,V[i]+1,W[i]);
add(V[i]+1,U[i]+1,W[i]);
}
dfsx(x,-1), dfsy(y,-1);
for(long long i=1;i<=n;i++)
g[i].clear();
for(long long i=0;i<=n*2;i++)
fa[i]=son[i]=del[i]=0;
long long sum=0,cnt=0,ans=calc(k);
for(long long i=y;i;i=fat[i])
{
inpath[i]=true;
if(distx[i]>disty[i]) swap(distx[i],disty[i]);
add(0,disty[i]-distx[i]);
k -= distx[i], sum++;
val[cnt+1].sum=disty[i]-distx[i];
cnt++;
}
long long realk=k;
if(k<0)
return ans;
for(long long i=1;i<=n;i++)
{
if(!inpath[i])
{
if(distx[i]>disty[i]) swap(distx[i],disty[i]);
add(distx[i],disty[i]-distx[i]);
val[cnt+2].sum=disty[i]-distx[i], val[cnt+1].sum=distx[i];
fa[cnt+2]=cnt+1, son[cnt+1]=cnt+2;
cnt += 2;
}
}
priority_queue <node> q;
for(long long i=1;i<=cnt;i++)
{
val[i].sz=1, val[i].id=i;
q.push(val[i]), a[i]=val[i].sum;
}
while(!q.empty())
{
node x=q.top();
q.pop();
if(del[x.id])
continue;
if(!fa[x.id] || del[fa[x.id]])
{
if(k>=x.sum)
{
k -= x.sum;
sum += x.sz;
if(x.sz==1)
del[x.id]=true;
else
del[x.id]=del[son[x.id]]=true;
continue;
}
else
break;
}
else
{
val[fa[x.id]].sz += val[x.id].sz, val[fa[x.id]].sum += x.sum;
q.push(val[fa[x.id]]);
}
}
for(long long i=1;;i++)
if(!check(i,realk))
return max(i-1,ans);
}
详细
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 93ms
memory: 72892kb
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:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 451
result:
ok
Test #2:
score: 0
Accepted
time: 119ms
memory: 79336kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 97133 170892 35489415917 114511 170892 730058 34783 114511 435023 34783 47301 562314 47301 162600 457629 44856 162600 365133 44856 133801 83016 117539 133801 124222 117539 128719 199821 77871 128719 703141 77871 133155 624331 7211 133155 138691 7211 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 650
result:
ok
Test #3:
score: 0
Accepted
time: 39ms
memory: 44184kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 200 1000 611 992 5736784 504 611 954658 504 936 219278 502 936 632439 393 502 177662 267 393 570266 267 291 941365 291 310 168052 310 765 253098 635 765 724932 274 635 842125 274 799 848645 39 799 433118 39 940 705598 553 940 564063 553 960 69665 917 960 6904...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 126 38 69 34 52 33 42 32 39 41 38 36 45 84 40 44 50 42 47 34 38 47 38 37 39 37 44 39 32 33 38 54 25 36 46 33 37 35 28 36 45 43 44 49 37 33 43 44 53 42 33 30 50 41 37 40 37 44 207 31 37 45 36 43 35 40 41 39 135 53 40 32 31 37 34 38 51 48 36 40 48 42 43 43 3...
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #4:
score: 9
Accepted
time: 3ms
memory: 41496kb
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
Wrong Answer
time: 1ms
memory: 42768kb
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 34
result:
wrong answer 1st lines differ - on the 1st token, expected: '26', found: '34'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #36:
score: 9
Accepted
time: 0ms
memory: 39868kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 9 0 2 2 1 2 3 2 3 3
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 6
result:
ok
Test #37:
score: 0
Accepted
time: 1ms
memory: 39796kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 8 0 2 2 1 2 3 2 3 100
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 5
result:
ok
Test #38:
score: 0
Accepted
time: 1ms
memory: 40620kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 8 0 4 84 0 1 1 1 2 29 2 3 29 3 4 1 4 5 20 2 6 20 3 7 1
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 9
result:
ok
Test #39:
score: -9
Wrong Answer
time: 1ms
memory: 40836kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 14 15 221112 8 10 15984 3 8 2664 6 10 5328 9 10 13320 5 10 23976 1 10 13320 3 4 5328 3 7 26640 3 11 23976 4 15 23976 6 17 18648 12 17 5328 11 13 13320 0 11 7992 15 16 5328 2 16 5328 13 14 2664
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 15
result:
wrong answer 1st lines differ - on the 1st token, expected: '14', found: '15'
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #4:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%