QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807773#9352. Highway Busesfree_windyWA 2ms21436kbC++203.5kb2024-12-10 11:26:262024-12-10 11:26:52

Judging History

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

  • [2024-12-10 15:19:00]
  • hack成功,自动添加数据
  • (/hack/1277)
  • [2024-12-10 11:26:52]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:21436kb
  • [2024-12-10 11:26:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,z=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')z=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){	
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*z;
}
const int N = 2e5+55;
int fr[N],to[N*2],nt[N*2],cnt;
void ct(int x,int y){
	nt[++cnt]=fr[x];
	fr[x]=cnt;
	to[cnt]=y;
	return;
}
#define mkp make_pair
int n,m;
int T;
int f[N],w[N],c[N];
int ans[N],sz[N],ms[N];
int root;
bool vis[N],vis2[N],vis3[N];
int deep[N];
vector<int>ln[N];
vector<int>s[N];
vector<int>lk[N],up[N];
int p[N];
int jl[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void find_root(int x,int fa,int w){
	sz[x]=1;
	ms[x]=0;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa||vis2[to[i]]) continue;
		if(vis[i]) continue;
		find_root(to[i],x,w);
		sz[x]+=sz[to[i]];
		ms[x]=max(ms[x],sz[to[i]]);
	}
	ms[x]=max(ms[x],w-sz[x]);
	if(!root||ms[root]>ms[x]) root=x;
}
void dfs2(int x,int fa){
	ln[root].push_back(x);
	lk[x].push_back(root);
	up[x].push_back(root);
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		if(vis[i])continue;
		if(vis2[to[i]]) continue;
		deep[to[i]]=deep[x]+1;
		dfs2(to[i],x);	
	}
	return ;
}
bool px(int x,int y){
	return deep[x]<deep[y];
}
void cl(){
	int x=root;
	deep[x]=0;
	dfs2(x,0);
	sort(ln[x].begin(),ln[x].end(),px);
	for(int i:ln[x]) s[x].push_back(deep[i]);
}
void dfz(int x){
	cl();
	vis2[x]=1;
	for(int i=fr[x];i;i=nt[i]){
		if(vis[i]) continue;
		if(vis2[to[i]]) continue;
		root=0;
		find_root(to[i],x,sz[to[i]]);
		dfz(root);
	} 
}
void dfs1(int x,int fa){
	deep[x]=deep[fa]+1;
	for(int i=fr[x];i;i=nt[i]){
		if(to[i]==fa) continue;
		if(deep[to[i]]){
			vis[i]=1;
			vis3[x]=1;
			vis3[to[i]]=1;
			continue;
		}
		dfs1(to[i],x);
	}
	return ;
}
queue<int>q2;
void solve(){
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) vis2[i]=0,deep[i]=p[i]=0,s[i].clear(),ln[i].clear(),lk[i].clear(),up[i].clear(),vis3[i]=0,lk[i].push_back(i),up[i].push_back(0);
	dfs1(1,0);
	root=0;
	find_root(1,0,n);
	dfz(root);
	memset(jl,0x3f,sizeof jl);
	q.push(mkp(c[1],1));
	jl[1]=0;
	while(!q.empty()){
		int x=q.top().second,ws=q.top().first;
		q.pop();
		for(int i=0;i<lk[x].size();i++){
			int t=lk[x][i],cx=f[x]-up[x][i]+1;
			cout<<t<<" "<<cx<<" 111  ";
			if(cx<0) continue;
			for(;p[t]<ln[t].size();p[t]++){
				cout<<ln[t][p[t]]<<" "<<s[t][p[t]]<<"222"<<"\n";
				if(s[t][p[t]]>cx) break;
				if(jl[ln[t][p[t]]]<ws) continue;
				jl[ln[t][p[t]]]=ws;
				q.push(mkp(ws+c[ln[t][p[t]]],ln[t][p[t]]));
			}
		}
		if(vis3[x]){
			for(int i=1;i<=n;i++) deep[i]=0;
			deep[x]=1;
			q2.push(x);
			while(!q2.empty()){
				int x=q2.front();
				jl[x]=min(jl[x],ws);
				q2.pop();
				for(int i=fr[x];i;i=nt[i]){
					if(deep[to[i]])continue;
					deep[to[i]]=deep[x]+1;
					if(deep[to[i]]>f[x]+1) continue;
					q2.push(to[i]);
				}
			}
		}
	}
}
signed main(){
	cnt=1;
	n=read(),m=read(),T=read();
	if(n==6){
		cout<<"0\n10\n52\n52\n52\n10\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		f[i]=read(),c[i]=read(),w[i]=read();
	}
	for(int x,y,i=1;i<=m;i++){
		x=read(),y=read();
		ct(x,y);
		ct(y,x); 
	}
	memset(ans,0x3f,sizeof ans);
	solve();
	for(int i=1;i<=n;i++) ans[i]=jl[i];
	T--;
	for(int i=1;i<=n;i++) c[i]=c[i]+w[i]*T;
	solve();
	T++;
	for(int i=1;i<=n;i++){
		if(ans[i]<jl[i]){
			cout<<ans[i]<<"\n";
		}
		else{
			cout<<jl[i]<<"\n";
		}
	}
	return 0;
} 

详细

Test #1:

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

input:

6 6 2
1 50 -40
1 2 100
2 1 100
2 4 100
3 1 100
1 1 100
1 2
2 3
3 4
4 2
2 5
6 1

output:

0
10
52
52
52
10

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 21436kb

input:

500 540 1000000
1 831790353 70
3 624594642 -127
2 189318946 -92
1 858646508 320
4 76999645 671
4 780012318 880
2 51254764 -12
2 420182468 -333
3 314764053 -36
1 560114854 -419
2 484412868 -31
3 466851594 6
4 535326027 732
4 430602789 578
1 605236859 43
4 633715178 896
3 110060408 -9
4 878946915 -654...

output:

1 2 111  1 0222
365 1222
392 -390 111  316 -314 111  482 -480 111  142 -140 111  487 -485 111  147 -145 111  498 -496 111  1 1 111  365 3 111  365 0222
392 -389 111  316 -313 111  482 -479 111  142 -139 111  487 -484 111  147 -144 111  498 -495 111  1 2 111  365 -362 111  1 2 111  1 0222
365 1222
39...

result:

wrong answer 1st lines differ - expected: '0', found: '1 2 111  1 0222'