QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696127#9315. Rainbow Bracket Sequence_Joanna_WA 1ms4036kbC++202.9kb2024-10-31 21:36:162024-10-31 21:36:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 21:36:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4036kb
  • [2024-10-31 21:36:16]
  • 提交

answer


#include <bits/stdc++.h>
#define marry return

#define int long long
#define lowbit(x) (x&-x)
inline int read(){  
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57)f=ch=='-'?-1:1,ch=getchar();
    while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=getchar();
    return x*f;}
using namespace std;

const int inf=1e9;
const int F=0;
const int mod=114514;

int S,T;

struct node{
    int nx,to,v,k;
}w[505];
int head[205];
int t=1;
void add(int a,int b,int v,int k)   
{
	// printf("%d %d %d\n",a,b,v);
	w[++t]={head[a],b,v,k},head[a]=t;
	w[++t]={head[b],a,0,-k},head[b]=t;	
}

struct point{
	int dis,p;
	const bool operator >(const point &s)
	const 	{	marry dis>s.dis;	}
};
int h[205],dis[205],frm[205];
priority_queue<point,vector<point>,greater<point>>q;
bool bfs()
{
	for(int i=1;i<=T;++i) //warning
		dis[i]=inf,frm[i]=-1;
	frm[S]=0;
	dis[S]=0;
	q.push({0,S});
	while(!q.empty())
	{
		auto s=q.top();
		q.pop();
		if(s.dis>dis[s.p])
			continue;
		dis[s.p]=s.dis;
		for(int i=head[s.p];i;i=w[i].nx)
		{
			if(!w[i].v)
				continue;
			int vi=w[i].to;
			if(dis[s.p]+h[vi]-h[s.p]+w[i].k>=dis[vi])
				continue;
			dis[vi]=dis[s.p]+h[vi]-h[s.p]+w[i].k;
			q.push({dis[vi],vi});
			frm[vi]=i;
		}
	}
	marry frm[T]!=-1;
}

bool vis[205];
void spfa()
{
	queue<int>q;
	q.push(S);
	for(int i=1;i<=T;++i)//warning
		dis[i]=inf;
	vis[S]=1,dis[S]=0;
	while(!q.empty())
	{
		int s=q.front();
		q.pop();
		vis[s]=0;
		for(int i=head[s];i;i=w[i].nx)
		{
			if(!w[i].v)
				continue;
			int vi=w[i].to;
			if(dis[vi]>dis[s]+w[i].k)
			{
				dis[vi]=dis[s]+w[i].k;
				if(!vis[vi])
					q.push(vi),
					vis[vi]=1;
			}
		}
	}
}

pair<int,int> minumcostflow()
{
	spfa();
	for(int i=1;i<=T;++i)//warning
		h[i]=dis[i];
	int res1=0,res2=0;
    while(bfs())
	{
		int mn=inf;
		for(int s=T;s!=S;)
		{
			int vi=s;
			s=w[frm[vi]^1].to;
			mn=min(mn,w[frm[vi]].v);	
		}
		res1+=mn;
		for(int s=T;s!=S;)
		{
			int vi=s;
			s=w[frm[vi]^1].to;
			res2+=mn*w[frm[vi]].k;
			w[frm[vi]].v-=mn;
			w[frm[vi]^1].v+=mn;
		}
		for(int i=1;i<=T;++i)//warning
			h[i]=dis[i];
	}
	marry {res1,res2};
}

void clear()
{
	t=1;
	for(int i=1;i<=T;++i)
		head[i]=0;
	S=T=0;
}

int n,m;
int a[105],b[105];
void solve()
{
	n=read(),m=read();
	clear();
	S=1;
	T=2;
	add(S,T,n,0);
	for(int i=1;i<=m;++i)
		b[i]=-read();
	
	for(int i=1;i<=2*n;++i)
		a[i]=read(),++b[a[i]];
	for(int i=1;i<=m;++i)
	{
		++T;
		add(2,T,b[i],0);
	}

	int sum=0;
	for(int i=1;i<=2*n;++i)
	{
		++T;
		int tep=read();
		sum+=tep;
		add(a[i]+2,T,1,tep);
	}
	for(int i=1;i<2*n;++i)
	{
		int p1=T-2*n+i,p2=T-2*n+i+1;
		add(p1,p2,i/2,0);
	}
	// printf("%d %d\n",S,T);
	auto ans=minumcostflow();
	// printf("%d %d\n",ans.first,ans.second);
	if(ans.first!=n)
		puts("-1");
	else
		printf("%lld\n",sum-ans.second);
}

signed main()
{
    int t=read();
	while(t--)
		solve();

    marry F;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

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: 1ms
memory: 4036kb

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
-1
-1
-1
1497027962
-1
2539318868
1013080942
-1
-1
-1
2231197660
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1467678317
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1373323696

result:

wrong answer 3rd numbers differ - expected: '2351080746', found: '-1'