QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735669#9431. The Quest for El DoradoNana7RE 27ms287268kbC++142.9kb2024-11-11 21:12:042024-11-11 21:12:04

Judging History

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

  • [2024-11-11 21:12:04]
  • 评测
  • 测评结果:RE
  • 用时:27ms
  • 内存:287268kb
  • [2024-11-11 21:12:04]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define I inline
#define int long long
using namespace std;

const int N = 500010;
struct Dat {
	int tim,dis,id;
	Dat(int _tim=0,int _dis=0,int _id=0) {
		tim=_tim; dis=_dis; id=_id;
	}
	bool operator > (const Dat &t) const {
		if(tim==t.tim) return dis<t.dis;
		return tim<t.tim;
	}
	bool operator < (const Dat &t) const {
		if(tim==t.tim) return dis>t.dis;
		return tim>t.tim;
	}
};
struct edge {
	int u,c,l;
	edge(int _t=0,int _c=0,int _l=0) {
		u=_t; c=_c; l=_l;
	}
};
struct tic {
	int a,b;
}a[N];
priority_queue<Dat> pq;
vector<edge> q[N];
vector<int> v[N],id[N],f[20][N];
int n,m,K,lg[N];
int vis[N];
Dat dis[N];

I bool big(Dat d1,Dat d2) {
	if(d1.tim>d2.tim) return 1;
	if(d1.dis>d2.dis) return 1;
}
I void pdeal() {
	for(int i=1;i<=m;++i) v[i].clear(),id[i].clear();
	for(int i=1;i<=m;++i)
		for(int j=0;j<=19;++j)
			f[i][j].clear();
	for(int i=1;i<=K;++i) {
		int c=a[i].a,l=a[i].b;
		v[c].push_back(l);
		id[c].push_back(i);
		for(int j=0;j<=19;++j) 
			f[c][j].push_back(l);
	}
	//cout<<"???"<<endl;
	for(int co=1;co<=m;++co) {
	//	cout<<"As"<<co<<' '<<v[co].size()<<endl;
		for(int j=0;j<19;++j) {
			for(int i=1;i+(1<<j)<=v[co].size();++i) {
				f[co][j+1][i-1]=max(f[co][j][i-1],f[co][j][i+(1<<j)-1]); 
			}
		}	
	}
}
I int query(int col,int tim,int len) {
	int p=lower_bound(id[col].begin(),id[col].end(),tim)-id[col].begin();
	if(p==id[col].size()) return -1;
	for(int i=19;i>=0;--i) {
		if(p+(1<<i)<=id[col].size()-1&&f[col][i][p]<len) p=p+(1<<i);
	}
	if(v[col][p]>=len) return id[col][p];
	else return -1;
}
I void dij() {
	for(int i=1;i<=n;++i) dis[i]=Dat(1e9,1e9,i),vis[i]=0;
	dis[1]=Dat(0,0,1); vis[1]=1;
	pq.push(dis[1]);
	while(!pq.empty()) {
		Dat k=pq.top(); pq.pop();
		int x=k.id;
		for(auto &t:q[x]) {
			int u=t.u,c=t.c,l=t.l;
			if(a[k.tim].a==c&&l+k.dis<=a[k.tim].b) {
				Dat upd=Dat(k.tim,k.dis+l,u);
				if(big(dis[u],upd)) {
					dis[u]=upd;
					if(!vis[u]) {
						vis[u]=1;
						pq.push(dis[u]);
					}
				}
			} else {
				int mk=query(c,k.tim+1,l);
				if(mk==-1) continue;
				Dat upd=Dat(mk,l,u);
				if(big(dis[u],upd)) {
					dis[u]=upd;
					if(!vis[u] ) {
						vis[u]=1;
						pq.push(dis[u]);
					}
				}
			}
		}
	}
}
I void print() {
	for(int i=1;i<=n;++i) {
		if(dis[i].tim==1e9) cout<<'0';
		else cout<<'1';
	}
	cout<<endl;
}
I void solve() {
	cin>>n>>m>>K;
	for(int i=1;i<=n;++i) q[i].clear();
	for(int i=1;i<=m;++i) {
		int u,v,c,l; cin>>u>>v>>c>>l;
		q[u].push_back(edge(v,c,l));
		q[v].push_back(edge(u,c,l));
	}
	for(int i=1;i<=K;++i) cin>>a[i].a>>a[i].b;
	pdeal();// cout<<"ps1"<<endl;
	dij();
	print();
}
signed main()
{

	int T; cin>>T;
	while(T--) {
		solve();
	}
}
/*
1
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


*/

詳細信息

Test #1:

score: 100
Accepted
time: 27ms
memory: 287268kb

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
Runtime Error

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:


result: