QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781211#9431. The Quest for El DoradohotdogsellerWA 19ms25576kbC++143.9kb2024-11-25 15:15:342024-11-25 15:15:35

Judging History

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

  • [2024-11-25 15:15:35]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:25576kb
  • [2024-11-25 15:15:34]
  • 提交

answer

#include<bits/stdc++.h>

#define maxn 500005
#define INF 1e18
#define int long long

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

struct edge{
	int to;
	int val;
	int c;
	int next;
}e[2*maxn];

int e_cnt=1,head[maxn];

void add(int u,int v,int w,int c){
	e[e_cnt].to=v;
	e[e_cnt].val=w;
	e[e_cnt].c=c;
	e[e_cnt].next=head[u];
	head[u]=e_cnt++;
}

int n,m,k;
int a[maxn],b[maxn];
pair<int,int> dis[maxn];//{用到的票,路程}

struct node{
	int x;
	pair<int,int> val;
};

node make_node(int x,int v1,int v2){
	node lre;lre.x=x;
	lre.val=make_pair(v1,v2);
	return lre;
}

bool operator <(node a,node b){
	if(a.val.first==b.val.first){
		return a.val.second>b.val.second;
	}
	return a.val.first>b.val.first;
}

priority_queue<node> pq;

bool okay(pair<int,int> p1,pair<int,int> p2){
	if(p1.first==p2.first){
		return p1.second<p2.second;
	}
	return p1.first<p2.first;
}//p1是否比p2更优 

int tot=1;
const int L=1,R=1e9;
int root[maxn];
int lc[2*maxn],rc[2*maxn],p[2*maxn];

void change(int x1,int x2,int l,int r,int goal,int val){
	if(l==r){
		p[x2]=val;
		return;
	}
	int mid=l+r>>1;
	if(goal<=mid){
		rc[x2]=rc[x1];
		lc[x2]=tot++;lc[lc[x2]]=rc[lc[x2]]=0;
		change(lc[x1],lc[x2],l,mid,goal,val);
	}else{
		lc[x2]=lc[x1];
		rc[x2]=tot++;lc[rc[x2]]=rc[rc[x2]]=0;
		change(rc[x1],rc[x2],mid+1,r,goal,val);
	}
}

int query(int x,int l,int r,int goal){
//	cout<<"x="<<x<<" of ["<<l<<","<<r<<"]"<<endl;
	if(l==r){
		return p[x];
	}
	int mid=l+r>>1;
	if(goal<=mid){
		if(lc[x]==0)return 0;
		return query(lc[x],l,mid,goal);
	}else{
		if(rc[x]==0)return 0;
		return query(rc[x],mid+1,r,goal);
	}
}

void show_tree(int x,int l,int r){
	cout<<"x="<<x<<" of ["<<l<<","<<r<<"]"<<endl;
	if(l!=r){
		int mid=l+r>>1;
		if(lc[x])show_tree(lc[x],l,mid);
		if(rc[x])show_tree(rc[x],mid+1,r);
	}else{
		cout<<"p="<<p[x]<<endl;
	}
}

void solve(){
	e_cnt=1;tot=1;
	lc[0]=rc[0]=0;p[0]=0;
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++){
		head[i]=0;dis[i]=make_pair(INF,INF);
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),c=read(),l=read();
		add(u,v,l,c);add(v,u,l,c);
	}
	
	for(int i=1;i<=k;i++){
		a[i]=read();b[i]=read();
	}
	
	root[k]=0;
	for(int i=k-1;i>=1;--i){
		root[i]=tot++;lc[root[i]]=rc[root[i]]=0;
		change(root[i+1],root[i],L,R,a[i+1],i+1);
	//	cout<<"show_tree "<<i<<endl;
	//	show_tree(root[i],L,R); 
	}
	
	pq.push(make_node(1,1,0));
	dis[1].first=1;dis[1].second=0;
	while(!pq.empty()){
		int x=pq.top().x;pair<int,int> val=pq.top().val;pq.pop();
		if(okay(dis[x],val))continue;
	//	cout<<"x="<<x<<endl;
		for(int i=head[x];i;i=e[i].next){
			int v=e[i].to,w=e[i].val,c=e[i].c;
			pair<int,int> nxt=val;
		//	cout<<" to "<<v<<" for edge {"<<w<<","<<c<<"}"<<endl;
			if(c==a[dis[x].first]&&w+dis[x].second<=b[dis[x].first]){
				nxt.second+=w;
				if(okay(nxt,dis[v])){
					dis[v]=nxt;
					pq.push(make_node(v,nxt.first,nxt.second));
				}
			}else{
			//	cout<<"query in tree "<<val.first<<" for "<<c<<endl;
				nxt.first=query(root[val.first],L,R,c);
			//	cout<<"change to "<<nxt.first<<endl;
				nxt.second=w;
				//换票 
				if(nxt.first&&w<=b[nxt.first]){
					if(okay(nxt,dis[v])){
						dis[v]=nxt;
						pq.push(make_node(v,nxt.first,nxt.second));
					}
				}
			}
		} 
	}
//	for(int i=1;i<=n;i++){
	//	cout<<"{"<<dis[i].first<<","<<dis[i].second<<"} "; 
//	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		if(dis[i].first==INF){
			putchar('0');
		}else{
			putchar('1');
		}
	}
	putchar('\n');
}

signed main(){
	
	int t=read();
	while(t--){
		solve();
	} 
	
	return 0;
}
/*
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: 0ms
memory: 20072kb

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: 19ms
memory: 25576kb

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:

1000000000000100000010000000000100000100000000
1000000000000001000000000000000000000000000000
1000000000000000000000000000000000000000000000
1001000000000000000000000010000000000000000000
1000000000000000000000000000000000000000000000
1001100010000000100000000000000001001010010
100000000000000000000...

result:

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