QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#754315#9431. The Quest for El DoradowsxcbWA 129ms6276kbC++172.1kb2024-11-16 14:44:432024-11-16 14:44:44

Judging History

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

  • [2024-11-16 14:44:44]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:6276kb
  • [2024-11-16 14:44:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
typedef vector<vector<ll>> Mat;
const int N=3e5+10,mod=998244353,inf=2e9+18;
const double pi=acos(-1.0),esp=1e-9;
const ll INF=1e18;

struct node{
	int u,col,v1;
	ll v2,c;
	bool operator<(const node &t)const{
		if(v1==t.v1) return t.v2<v2;
		return v1<t.v1;
	}
};
void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<int>>pos(m+1);
	vector<vector<ll>>sum(m+1);
	vector<int>vis(n+1);
	vector< vector< array<int,3> > >e(n+1);
	pair<int,int>sc={inf,inf};
	vector<pair<int,int>>dis(n+1,sc);
	dis[1]={0,0};
	for(int i=1;i<=m;i++){
		int u,v,c,l;
		cin>>u>>v>>c>>l;
		e[u].pb({v,c,l});
		e[v].pb({u,c,l});
		pos[i].pb(0);
		sum[i].pb(0);
	}
	for(int i=1;i<=k;i++){
		int a,b;
		cin>>a>>b;
		pos[a].pb(i);
		sum[a].pb(b);
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<(int)pos[i].size();j++){
			sum[i][j]+=sum[i][j-1];
		}
	}
	priority_queue<node>q;
	q.push({1,0,0,0,0});
	while(q.size()){
		auto [u,col1,v1,v2,c]=q.top();
		q.pop();
		if(vis[u])continue;
		//cout<<u<<' '<<v1<<' '<<v2<<' '<<c<<'\n';
		vis[u]=1;
		for(auto [v,col2,l]:e[u]){
			if(col1==col2&&c>=l){
				if(dis[v].fi>v1||(dis[v].fi==v1&&dis[v].se>v2+l))
				{
					//cout<<v<<' ';
					dis[v]={v1,v2+l};
					q.push({v,col1,v1,v2+l,c-l});
				}
				continue;
			}
			int p1=upper_bound(pos[col2].begin(),pos[col2].end(),v1)-pos[col2].begin();
			if(p1==(int)pos[col2].size())continue;
			p1--;
			int p2=lower_bound(sum[col2].begin(),sum[col2].end(),l+sum[col2][p1])-sum[col2].begin();
			if(p2==(int)sum[col2].size())continue;
			int x=sum[col2][p2]-sum[col2][p1]-l,z=pos[col2][p2];
			int y=l+sum[col2][p1]-sum[col2][p2-1];
			if(dis[v].fi>z||(dis[v].fi==z&&dis[v].se>y))
			{
				dis[v]={z,y};
				q.push({v,col2,z,y,x});
				//cout<<v<<' ';
			}
		}
		//cout<<'\n';
	}
	for(int i=1;i<=n;i++){
		if(dis[i].fi<=k)cout<<1;
		else cout<<0;
	}
	cout<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

詳細信息

Test #1:

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

input:

2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30
3 1 1
2 3 1 10
1 100

output:

11011
100

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 129ms
memory: 6276kb

input:

1110
46 80 30
44 23 5 46
10 28 1 64
32 34 3 40
9 36 1 26
15 14 5 95
38 19 2 34
2 17 4 183
10 38 2 81
5 15 2 83
31 38 3 100
40 30 1 53
41 10 1 193
29 20 5 18
14 41 3 78
8 16 5 74
46 13 3 78
44 28 3 45
1 40 3 133
5 32 1 108
22 26 2 83
10 38 1 77
11 40 1 11
17 21 2 66
41 46 3 98
9 36 2 25
40 18 1 19
27...

output:

1110110111110111110010110101011100100101001010
1111010011111111011111110000011111011111011010
1000000000000000000000000000000000000000000000
1111010101111111111110111111100111011011111111
1111000000010000000100101010110001101011000111
1011101010110111111011111011110011111110111
101010100000000000010...

result:

wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1110110111110111110010110101011100100101001010'