QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164615 | #7118. Closing Time | unputdownable | Compile Error | / | / | C++17 | 2.4kb | 2023-09-05 11:11:53 | 2023-09-05 11:11:54 |
Judging History
你现在查看的是测评时间为 2023-09-05 11:11:54 的历史记录
- [2024-04-28 07:28:05]
- 管理员手动重测本题所有提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-09-05 11:11:54]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-09-05 11:11:53]
- 提交
answer
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include "closing.h"
#include <bits/stdc++.h>
#define int long long
#define i64 long long
#define pii pair <i64, i64>
using namespace std;
vector <pii> E[200005];
i64 depx[200005],depy[200005];
i64 sig[400005],cnt1,cnt2;
pii val[200005];
i64 vvv[400005];
inline void dfs(int x,int f,i64*dep) {
for(pii e : E[x]) {
if(e.first==f) continue;
dep[e.first]=dep[x]+e.second;
dfs(e.first,x,dep);
}
}
inline void check(int&R,i64&sum,i64 lim) { if(lim<0) return R=-1000000,void(); while(sum>lim) sum-=sig[R--]; }
int max_score(int n, int x, int y,i64 k, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
for(int i=0; i<n; ++i) E[i].clear(); cnt1=cnt2=0; int k0=k;
int m=U.size();
for(int i=0; i<m; ++i) E[U[i]].emplace_back(V[i],W[i]);
for(int i=0; i<m; ++i) E[V[i]].emplace_back(U[i],W[i]);
dfs(x,-1,depx);
dfs(y,-1,depy);
// for(int i=0; i<n; ++i) cerr<<depx[i]<<' '; cerr<<endl;
// for(int i=0; i<n; ++i) cerr<<depy[i]<<' '; cerr<<endl;
int cnt=0;
for(int i=0,a,b; i<n; ++i) {
vvv[i+1]=depx[i];
vvv[i+n+1]=depy[i];
if(depx[i]+depy[i]==depx[y]) {
k-=min(depx[i],depy[i]);
sig[++cnt1]=max(depx[i],depy[i])-min(depx[i],depy[i]);
++cnt;
continue;
}
if(depx[i]>depy[i]) a=depy[i],b=depx[i]-a;
else a=depx[i],b=depy[i]-a;
if(a<b) sig[++cnt1]=a,sig[++cnt1]=b;
else val[++cnt2]=(pii){a+b,a};
}
sort(val+1,val+cnt2+1);
sort(sig+1,sig+cnt1+1);
sort(vvv+1,vvv+2*n+1); vvv[2*n+1]=k0+1;
int p=0; i64 s1=0;
while(s1+vvv[p+1]<=k0) s1+=vvv[++p];
int Ans=p;
// cerr<<Ans<<"----------"<<endl;
// for(int i=1; i<=cnt1; ++i) cerr<<sig[i]<<' '; cerr<<endl;
// for(int i=1; i<=cnt2; ++i) cerr<<val[i].first<<' '<<val[i].second<<'|'; cerr<<endl;
int R=0; i64 sum=0; sig[cnt1+1]=k+1;
while(sum+sig[R+1]<=k) sum+=sig[++R];
// cerr<<R<<' '<<sum<<endl;
if(k>=0) Ans=max(Ans,R+cnt);
// cerr<<"------------------"<<endl;
if(k>=0) for(int i=1; i<=cnt2; ++i) {
check(R,sum,k-val[i].second),Ans=max(Ans,2*i+R+cnt-1);
check(R,sum,k-=val[i].first),Ans=max(Ans,2*i+R+cnt);
}
return Ans;
}
详细
/usr/bin/ld: /tmp/ccywxBYc.o: in function `main': implementer.cpp:(.text.startup+0x775): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)' collect2: error: ld returned 1 exit status