QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#577479#9345. Artful PaintingszrtWA 1ms3804kbC++141.9kb2024-09-20 11:48:092024-09-20 11:48:11

Judging History

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

  • [2024-09-20 11:48:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2024-09-20 11:48:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,flg=0;
	char c=getchar();
	while(c<'0'||c>'9')flg|=c=='-',c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
	return flg?-ret:ret;
}
inline void write(int x,bool flg){
	char a[21];
	if(!x)putchar('0');
	if(x<0)putchar('-'),x=-x;
	int cnt=0;
	while(x){
		a[++cnt]=x%10+'0';
		x/=10;
	}
	while(cnt)putchar(a[cnt--]);
	putchar(flg?'\n':' ');
	return ;
}
#define maxn 12010
#define maxm 12012
int n,m1,m2;
int he[maxn],ver[maxm],nxt[maxm],edge[maxm],tot;
void add(int x,int y,int z){
	ver[++tot]=y;nxt[tot]=he[x];he[x]=tot;edge[tot]=z;
//	cout<<"ee"<<x<<" "<<y<<" "<<z<<endl; 
}
int dis[maxn],vis[maxn],q[maxn],hd,tl;
void spfa(){
	hd=1,tl=0;
	for(int i=1;i<=2*n+1;i++)dis[i]=0,q[++tl]=i,vis[i]=1;
	while(hd<=tl){
		int x=q[hd++];
	//	cout<<x<<endl;
		vis[x]=0;
		for(int i=he[x];i;i=nxt[i]){
			int y=ver[i];
			if(dis[y]<dis[x]+edge[i]){
				dis[y]=dis[x]+edge[i];
				if(!vis[y])
					vis[y]=1,q[++tl]=y;
			}
		}
	}
	return ;
}
int cc[maxn];
void solve(){
	n=read(),m1=read(),m2=read();
	
	tot=1;
	for(int i=1;i<=2*n+1;i++)he[i]=dis[i]=0;
	for(int i=1,u,v,w;i<=m1;i++){
		u=read(),v=read(),w=read();
		add(u,v+1,w);
	}
	for(int i=1,u,v,w;i<=m2;i++){
		u=read(),v=read(),w=read();
		add(v+1,u+n,w);
	}
	for(int i=1;i<=2*n;i++){
		add(i,i+1,0); 
	}
	int l=0,r=n,ans=n;
	while(l<=r){
		int mid(l+r>>1);
		int cun=tot;
		for(int i=1;i<=2*n+1;i++)cc[i]=he[i];
		for(int i=2;i<=n+1;i++){
			add(i,i+n,mid);
		}
		spfa();
		tot=cun;
		for(int i=1;i<=2*n+1;i++)he[i]=cc[i];
	//	cout<<mid<<":"<<endl;
//		for(int i=1;i<=2*n+1;i++){
//			write(dis[i],1);
//		}
		//cout<<dis[2*n+1]
		if(dis[2*n+1]-dis[n+1]>mid){
			l=mid+1;
		}else ans=mid,r=mid-1;
	}
	write(ans,1);
}
int main(){
	int T=read();
	while(T--)solve(); 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
3 1 1
1 2 1
2 2 1

output:

1

result:

ok single line: '1'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3804kb

input:

1
1000 500 500
479 860 170
73 939 25
363 772 30
185 584 89
326 482 10
784 949 23
384 740 114
233 693 45
167 724 211
217 436 95
46 701 153
138 585 67
321 388 11
114 890 194
407 854 74
438 845 117
9 718 259
393 576 35
182 707 257
451 766 136
150 382 31
468 785 40
202 490 46
326 815 59
272 441 77
123 8...

output:

476

result:

wrong answer 1st lines differ - expected: '492', found: '476'