QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #631587 | #9457. Prime Set | ucup-team896# | AC ✓ | 69ms | 25144kb | C++14 | 2.5kb | 2024-10-12 08:59:39 | 2024-10-12 08:59:39 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
template<class T,int N>struct Dinic{
const T INF=numeric_limits<T>::max()/2;
int n,s,t,h[N],d[N];
vector<tuple<int,T,int>>G[N];
inline void add(const int&u,const int&v,const T&w,const T&rw=0){
const int ru=G[v].size(),rv=G[u].size();
G[u].emplace_back(v,w,ru),G[v].emplace_back(u,rw,rv);
}
inline bool bfs(){
int ql=0,qr=1;static int Q[N];
for(fill(d+1,d+n+1,-1),d[Q[1]=s]=0;ql<qr;){
int u=Q[++ql];h[u]=0;if(u==t)return 1;
for(auto [v,w,_]:G[u])if(w&&d[v]<0)d[Q[++qr]=v]=d[u]+1;
}
return 0;
}
inline T dfs(const int&u,T mf){
if(u==t)return mf;
T z=0;
for(int&i=h[u];i<G[u].size();++i){
const auto [v,w,j]=G[u][i];
if(d[u]+1==d[v]&&w){
const T dd=dfs(v,min(mf,w));
get<1>(G[u][i])-=dd,mf-=dd,get<1>(G[v][j])+=dd,z+=dd;
if(!mf)return z;
}
}
return d[u]=-1,z;
}
inline void init(const int&_n,const int&_s,const int&_t){
n=_n,s=_s,t=_t;for(int i=1;i<=n;++i)G[i].clear();
}
inline T flow(){T z=0;while(bfs())z+=dfs(s,INF);return z;}
};
const int N=3e3+5,M=2e6+5,INF=1e9;
int n,m,k;
int a[N];
Dinic<int,N>Gr;
map<int,int>cnt,id;
int pn,vp[M],pr[M];
inline void sieve(const int&n){
for(int i=2;i<=n;++i){
if(!vp[i])pr[++pn]=i;
for(int j=1,k;j<=pn&&(k=i*pr[j])<=n;++j){
vp[k]=1;
if(i%pr[j]==0)break;
}
}
}
inline void MAIN(){
cin>>n>>k,k=min(k,n),m=0,cnt.clear(),id.clear(),cnt[1];
for(int i=1;i<=n;++i)cin>>a[i],++cnt[a[i]];
for(auto [x,y]:cnt)id[x]=++m;
Gr.init(m+2,m+1,m+2);
for(auto [x,xi]:id)if(x!=1){
if(x&1){
Gr.add(Gr.s,xi,cnt[x]);
for(auto [z,zi]:id)if(!vp[x+z])Gr.add(xi,zi,INF);
}
else Gr.add(xi,Gr.t,cnt[x]);
}
auto mf=Gr.flow();
Gr.add(Gr.s,id[1],cnt[1]);
for(auto [x,xi]:id)if(x!=1&&!vp[x+1])Gr.add(id[1],xi,INF);
mf+=Gr.flow();
for(auto [v,w,_]:Gr.G[Gr.s])if(v==id[1])mf+=w/2;
if(k<=mf)cout<<k*2<<'\n';
else{
int all=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)if(j!=i)
if(!vp[a[i]+a[j]]){++all;break;}
cout<<min(k+mf,all)<<'\n';
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
sieve(2e6);
int t=1;cin>>t;while(t--)MAIN();
return 0;
}
/*
4
4 2
2 3 4 5
5 3
3 4 12 3 6
6 3
1 3 6 8 1 1
1 0
1
*/
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 12144kb
input:
4 4 2 2 3 4 5 5 3 3 4 12 3 6 6 3 1 3 6 8 1 1 1 0 1
output:
4 3 6 0
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 69ms
memory: 25144kb
input:
110 3 3 2 2 2 3 1 1 1 1 3 2 1 1 1 3 3 1 1 1 4 2 1 1 1 1 10 7 1 1 1 2 4 6 8 10 12 14 18 1 10 5 9 4 10 7 2 4 9 1 6 1 4 9 2 4 9 7 19 5 1 6 1 8 8 1 5 10 9 2 10 2 1 9 6 10 4 3 6 14 4 6 6 8 9 5 3 4 9 2 2 1 10 10 1 15 10 5 4 2 4 10 1 8 4 10 3 10 3 7 10 4 17 5 10 7 2 4 3 1 10 8 2 8 3 4 1 1 1 1 1 20 6 8 4 6 ...
output:
0 2 3 3 4 8 2 10 8 15 10 12 10 10 12 16 10 10 12 16 14 13 13 14 17 0 19 12 12 11 16 10 19 2 12 10 5 14 10 10 13 2 18 2 4 4 11 8 11 8 0 10 10 0 10 0 8 15 12 11 13 18 10 17 9 8 20 19 13 6 4 6 11 9 13 11 6 2 8 12 17 14 6 2 20 2 18 17 6 2 10 0 7 16 2 2 0 2 18 14 11 8 4 6 0 19 890 204 2746 2372
result:
ok 110 lines
Extra Test:
score: 0
Extra Test Passed