QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#39081#1269. New EquipmentswyhaoWA 5ms3304kbC++2.6kb2022-07-08 13:07:282022-07-08 13:07:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-08 13:07:29]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3304kb
  • [2022-07-08 13:07:28]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int N=55,N1=3005,M=20005;
typedef long long ll;
int TT,n,m,S,T,cnt,num;
ll a[N],b[N],c[N],cst[M];
int to[M],nxt[M],f[M],h[N1];
void add(int i,int x,int y,int z,ll w){
//	printf("%d %d %d %lld\n",x,y,z,w);
	to[i]=y;f[i]=z;nxt[i]=h[x];cst[i]=w;h[x]=i;
}
map<int,int>Map;
ll F(int i,int j){
	return a[i]*j*j+b[i]*j+c[i];
}
struct node{
	int val;ll key;
	bool operator<(const node a)const{
		return key>a.key;
	}
}d[N1],p;
int tot;
bool cmp(node x,node y){
	return x.key<y.key;
}
void get1(int i,int &l,int &r){
	if(2*a[i]>=-b[i]){
		l=1;r=n;
		return;
	}
	if(2*a[i]*m<=-b[i]){
		r=m;l=m-n+1;
		return;
	}
	tot=1;int t=-b[i]/(a[i]*2);
//	printf("%d\n",t);
	d[1].val=t;d[1].key=F(i,t);
	for(int i=1;i<=n;i++){
		if(t-i>=1){
			tot++;
			d[tot].val=t-i;
			d[tot].key=F(i,t-i);
		}
		if(t+i<=m){
			tot++;
			d[tot].val=t+i;
			d[tot].key=F(i,t+i);
		}
	}
	sort(d+1,d+tot+1,cmp);
	l=m;r=1;
	for(int i=1;i<=n;i++){
		if(d[i].val<l) l=d[i].val;
		if(d[i].val>r) r=d[i].val;
	}
}
priority_queue<node>Q;
ll dis[N1];
int pre[N1];
bool vis[N1];
ll dfs(){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	while(!Q.empty()) Q.pop();
	dis[S]=0;pre[S]=-1;
	p.val=S;p.key=0;Q.push(p);
	while(!Q.empty()){
		int x=Q.top().val;Q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		if(x==T) return dis[T];
		for(int i=h[x],y;i;i=nxt[i]){
			y=to[i];
			if(vis[y]) continue;
			if(f[i] and dis[y]>dis[x]+cst[i]){
				dis[y]=dis[x]+cst[i];
				p.val=y;p.key=dis[y];
				Q.push(p);
				pre[y]=i;
			}
		}
	}
	return 0x3f3f3f3f3f3f3f3f;
}
void path(){
	for(int t=pre[T];~t;t=pre[to[t^1]]){
		f[t]--;f[t^1]++;
	}
}
int main(){
//	freopen("ex1.in","r",stdin);
	scanf("%d",&TT);
	while(TT--){
		scanf("%d%d",&n,&m);num=n;
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		}
		Map.clear();cnt=1;
		for(int i=1,l,r,k;i<=n;i++){
			get1(i,l,r);
//			printf("%d %d\n",l,r);
			for(int j=l;j<=r;j++){
				if(!Map[j]) Map[j]=++num;
				k=Map[j];ll w=F(i,j);
				add(++cnt,i,k,1,w);
				add(++cnt,k,i,0,-w);
			}
		}
		S=num+1;T=S+1;
		for(int i=1;i<=n;i++){
			add(++cnt,S,i,1,0);
			add(++cnt,i,S,0,0);
		}
		for(int i=n+1;i<=num;i++){
			add(++cnt,i,T,1,0);
			add(++cnt,T,i,0,0);
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			ll k=dfs();
			if(k!=0x3f3f3f3f3f3f3f3f){
				ans+=k;path();
				printf("%lld ",ans);
			}else{
				for(;i<=n;i++) printf("%lld ",ans);
				break;
			}
			if(n==50 and i==49) return 0;
		}
		puts("");
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3288kb

input:

1
3 5
2 3 10
2 -3 10
1 -1 4

output:

4 15 37 

result:

ok single line: '4 15 37 '

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 3304kb

input:

10
50 50
2 -16 79
8 -21 54
8 -1 3
1 -7 47
5 -20 89
1 -2 47
2 -10 26
10 31 28
2 -16 37
6 -16 44
2 -8 100
3 -26 65
3 -6 91
10 -33 56
2 -7 22
2 -12 74
1 -3 7
7 -30 51
1 -4 8
1 -10 62
2 -5 5
1 -3 38
7 -32 57
4 -24 65
1 -8 97
7 -28 71
5 -13 71
2 -14 49
6 -33 100
2 7 69
8 -22 38
5 -23 88
7 20 57
7 -11 83
...

output:

2 4 9 14 24 40 72 117 170 239 327 445 592 771 972 1202 1467 1772 2117 2506 2954 3461 4035 4690 5415 6223 7137 8145 9272 10499 11858 13366 15003 16798 18736 20810 23058 25517 28172 31062 34194 37566 41209 45136 49371 53924 58847 64143 69813 

result:

wrong answer 1st lines differ - expected: '2 4 9 14 24 40 72 117 170 239 ...1 53924 58847 64143 69813 75884', found: '2 4 9 14 24 40 72 117 170 239 ... 49371 53924 58847 64143 69813 '