QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#574056#9315. Rainbow Bracket SequenceWolamWA 1ms3696kbC++172.1kb2024-09-18 20:40:402024-09-18 20:40:44

Judging History

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

  • [2024-09-18 20:40:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3696kb
  • [2024-09-18 20:40:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t;
int l[205];
int c[205],v[205];
int vis[505];
int head[505],tot;
int cur[505],dis[505];
struct ss{
	int node,nxt,w,f;
}e[5005];
void add(int u,int v,int w,int f)
{
	e[++tot]=(ss){v,head[u],w,f};
	head[u]=tot;
	e[++tot]=(ss){u,head[v],0,-f};
	head[v]=tot;
}
bool spfa()
{
	for(int i=s;i<=t;i++)
		dis[i]=-inf;
	queue<int> q;
	q.push(s);dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		//cerr<<x<<" "<<dis[x]<<endl;
		for(int i=head[x];i;i=e[i].nxt)
		{
			if(!e[i].w)continue;
			int y=e[i].node;
			if(dis[x]+e[i].f>dis[y])
			{
				dis[y]=dis[x]+e[i].f;
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	return dis[t]!=-inf;
}
int cost;
int dinic(int x,int now)
{
	//cerr<<x<<endl;
	if(x==t||!now)return now;
	int ans=0;
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		cur[x]=i;
		if(!e[i].w)continue;
		int y=e[i].node;
		if(!vis[y]&&dis[y]==dis[x]+e[i].f)
		{
			int v=dinic(y,min(now-ans,e[i].w));
			e[i].w-=v;
			e[i^1].w+=v;
			ans+=v;
			cost+=v*e[i].f;
			if(ans==now)break;
		}
	}
	vis[x]=0;
	return ans;
}
void sol()
{
	cin>>n>>m;
	s=0;
	t=n+n+m+2;
	tot=1;
	for(int i=s;i<=t;i++)
		head[i]=0;
	int lev=n;
	for(int i=1;i<=m;i++)
	{
		cin>>l[i];
		add(s,n+n+i,l[i],0);
		lev-=l[i];
	}
	for(int i=1;i<=n+n;i++)
	{
		cin>>c[i];
	}
	for(int i=1;i<=n+n;i++)
	{
		cin>>v[i];
		add(n+n+c[i],i,1,v[i]);
		add(i,t,1,0);
		if(i<n+n)
			add(i,i+1,inf,0);
		if(i%2==0)
			add(s,i,1,0);
	}
	//cerr<<"graph"<<endl;
	if(lev<0)
	{
		cout<<"-1\n";
		return;
	}
	add(s,n+n+m+1,lev,0);
	add(n+n+m+1,1,lev,0);
	cost=0;
	int ans=0;
	while(spfa())
	{
		for(int i=s;i<=t;i++)
			cur[i]=head[i];
		ans+=dinic(s,inf);
	}
	if(ans!=n+n)cost=-1;
	cout<<cost<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
		sol();
}
/*
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*/

詳細信息

Test #1:

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

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: 3696kb

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
1649648670
1812906175
-1
-1
831452391
2539318868
1013080942
1097019708
-1
-1
2231197660
758225925
0
2812012416
-1
841935645
5689642167
1345740508
-1
1988904333
-1
999388067
5268471900
0
1375278074
-1
4236865447
0
883992368
839769227
-1
3576403472
-1
856364894
2713025914
299682359
495542...

result:

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