QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#565696 | #9315. Rainbow Bracket Sequence | xxqz | WA | 9ms | 49796kb | C++17 | 3.5kb | 2024-09-15 22:01:52 | 2024-09-15 22:01:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N,S,T;
constexpr int maxn(1500000);
constexpr int inf = 0x3f3f3f3f;
const int MAX=1e9;
struct e{
int v,id;
};
vector<e> ed[maxn];
int val[550001],cost[550001],cnt=0;
void add(int u,int v,int w,int c){
val[cnt]=w;cost[cnt]=c;
ed[u].push_back((e){v,cnt++});
val[cnt]=0;cost[cnt]=-c;
ed[v].push_back((e){u,cnt++});
}
int las[maxn];ll d[maxn];
bool vis[maxn];
ll money=0;
bool bfs1(){
for(int i=0;i<=N+10;i++) d[i]=0;
queue<int> q;
q.push(S);
d[S]=1;
while(!q.empty()){
int x=q.front(); q.pop();
vis[x]=0;
for(auto v:ed[x]){
if(!val[v.id]) continue;
if(!d[v.v]){
d[v.v] = d[x]+1;
if(!vis[v.v])q.push(v.v),vis[v.v]=1;
}
}
}
return d[T];
}
int dfs1(int rt,int water){
if(rt==T) return water;
int flow=0;
for(auto&x:ed[rt]){
if(!val[x.id]||(d[x.v]!=d[rt]+1)) continue;
int c=dfs1(x.v,min(water,val[x.id]));
flow+=c;
water-=c;
val[x.id]-=c;
val[x.id^1]+=c;
money+=1ll*cost[x.id]*c;
if(!water) break;
}
if(!flow) d[rt] = 0;
return flow;
}
bool bfs2(){
for(int i=0;i<=N+10;i++) d[i]=0x3f3f3f3f3f3f3f3fll;
queue<int> q;
q.push(S);
d[S]=0;
while(!q.empty()){
int x=q.front(); q.pop();
vis[x]=0;
for(auto v:ed[x]){
if(!val[v.id]) continue;
if(cost[v.id]+d[x]<d[v.v]){
d[v.v] = d[x]+cost[v.id];
las[v.v]=x;
if(!vis[v.v])q.push(v.v),vis[v.v]=1;
}
}
}
return d[T]<0x3f3f3f3f3f3f3f3f;
}
int dfs2(int rt,int water){
if(rt==T) return water;
int flow=0;
for(auto&x:ed[rt]){
if(!val[x.id]||(las[x.v]!=rt)) continue;
int c=dfs2(x.v,min(water,val[x.id]));
flow+=c;
water-=c;
val[x.id]-=c;
val[x.id^1]+=c;
money+=1ll*cost[x.id]*c;
if(!water) break;
}
if(!flow) d[rt] = 0x3f3f3f3f3f3f3f3f;
return flow;
}
int solve1(){
int ans=0;
while(bfs1()){
int t=dfs1(S,inf);
ans+=t;
}
return ans;
}
int solve2(){
int ans=0;
while(bfs2()){
int t=dfs2(S,inf);
ans+=t;
}
return ans;
}
int in[maxn],out[maxn];
void _add(int u,int v,int l,int r,int c){
in[v]+=l;out[u]+=l;
add(u,v,r-l,c);
}
int build(){
S=N+2;T=N+3;
int sum=0;
for(int i=0;i<=N+1;i++){
if(in[i]>out[i]){
add(S,i,in[i]-out[i],0);
sum+=in[i]-out[i];
}else if(in[i]<out[i]){
add(i,T,out[i]-in[i],0);
}
}
return sum;
}
int pl[1005],pc[2005],pv[2005];
void work(bool op=0){
int n,m;money=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&pl[i]);
for(int i=1;i<=2*n;i++)scanf("%d",&pc[i]);
for(int i=1;i<=2*n;i++)scanf("%d",&pv[i]);
if(op)
for(int i=1;i<=2*n;i++)printf("%d",pv[i]);
if(op)exit(0);
N=m+4*n;
int s=0,t=N+1;
for(int i=1;i<=m;i++)_add(s,i,pl[i],2*n,0);
for(int i=1;i<=2*n;i++){
_add(pc[i],m+i,0,1,MAX-pv[i]);
_add(m+i,m+2*n+i,0,1,0);
}
for(int i=1;i<2*n;i++){
_add(m+2*n+i,m+2*n+i+1,(i+1)/2,n,0);
}
_add(m+4*n,t,n,n,0);
_add(t,s,0,inf,0);
int sum=build();
if(solve1()!=sum) cout<<-1<<'\n';
else{
int ans;
for(auto x:ed[t]){
if(x.v==s) ans=val[x.id^1],val[x.id]=val[x.id^1]=0;
}
// for(int i=1;i<cnt;i+=2) val[i]=0;
S=s,T=t;
ans+=solve2();
cout<<1ll*n*MAX-money<<'\n';
}
for(int i=0;i<=cnt;++i) val[i]=0;
cnt=0;
for(int i=0;i<=N+3;++i){
in[i]=out[i]=0;
ed[i].clear();
}
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++){
work(i==3);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 49796kb
input:
2 3 2 1 2 1 2 2 2 1 2 3 1 4 2 2 1 3 2 2 2 1 2 2 2 1 2 3 1 4 2 2 1
output:
9 -1
result:
ok 2 number(s): "9 -1"
Test #2:
score: -100
Wrong Answer
time: 9ms
memory: 49704kb
input:
50 8 6 0 2 2 0 3 1 3 5 1 1 5 3 5 2 3 2 2 1 2 2 4 6 998133227 879226371 59632864 356493387 62611196 827258251 296576565 204244054 812713672 780267148 614679390 447700005 102067050 544546349 116002772 761999375 1 1 1 1 1 343766215 374461155 3 1 2 1 1 1 1 1 1 796323508 303640854 701432076 853325162 610...
output:
-1 343766215 79632350830364085470143207685332516261071418171459320
result:
wrong output format Expected integer, but "79632350830364085470143207685332516261071418171459320" found