QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#707820#9431. The Quest for El DoradochenjueWA 106ms35704kbC++202.4kb2024-11-03 17:40:452024-11-03 17:40:47

Judging History

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

  • [2024-11-03 17:40:47]
  • 评测
  • 测评结果:WA
  • 用时:106ms
  • 内存:35704kb
  • [2024-11-03 17:40:45]
  • 提交

answer

#include<bits/stdc++.h> 
using namespace std;
#define int long long 
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dep(i,l,r) for(int i=l;i>=r;i--)
using pii=array<int,4>;
using pi2=array<int,2>;
const int N=5e5+10;
const int M=2e6+20;
const int inf=1e9+100;
int n,m,k;
vector<pi2>oo[N];
struct node{
	int n;
	vector<vector<int>>dp;
	void init(vector<pi2>&a){
		dp.resize(n+5,vector<int>(22,0));
		rep(i,1,n){
			dp[i][0]=a[i][1];
		}
		rep(k,1,20){
			for(int s=1;s+(1<<k)<=n+1;s++){
				dp[s][k]=max(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
			}
		}
	}
	int query(int L,int R){
		int k=log2(R-L+1);
		int x=max(dp[L][k],dp[R-(1<<k)+1][k]);
		return x;
	}
}st[N];
int head[N],cnt=1,ver[M],nex[M],w[M],c[M];
void add(int u,int v,int C,int W){
    ver[cnt]=v;
    w[cnt]=W;
	c[cnt]=C;
    nex[cnt]=head[u];
    head[u]=cnt++;
}
bool vis[N];
void dij(int x){
    priority_queue<pii,vector<pii>,greater<pii>>p;
    p.push({0,0,-1,x});//时间,容量,公司,in
    while(p.size()){
        auto [x,y,z,in]=p.top();p.pop();
        if(vis[in])continue;
        vis[in]=1;
        for(int i=head[in];i>0;i=nex[i]){
            int v=ver[i],C=c[i],W=w[i];//地点,公司,代价
			if(C==z&&y>=W){
				p.push({x,y-W,C,v});continue;
			}
			pi2 dd={x+1,0};
			int l=lower_bound(oo[C].begin(),oo[C].end(),dd)-oo[C].begin();
			int r=oo[C].size();
			if(r==0)continue;
			while(l<r){
				int mid=l+r>>1;
				if(st[C].query(l,mid)>=W){
					r=mid;
				}
				else{
					l=mid+1;
				}
			}
			int d=st[C].query(l,l);
			if(d>=W){
				p.push({oo[C][l][0],d-W,C,v});
			}
        }
    }
	rep(i,1,n){
		if(vis[i])cout<<1;
		else cout<<0;
	}
	cout<<endl;
}
void clear(){
	cnt=1;
	rep(i,1,n){
		vis[i]=0;
		head[i]=0;	
	}
	rep(i,1,m){
		oo[i].clear();
		oo[i].push_back({-1,-1});
	}
}
void solve(){
    cin>>n>>m>>k;
	clear();
	rep(i,1,m){
		int u,v,c,w;cin>>u>>v>>c>>w;
		add(u,v,c,w);
		add(v,u,c,w);
	}
	rep(i,1,k){
		int col,dis;cin>>col>>dis;
		oo[col].push_back({i,dis});
	}
	rep(i,1,m){//最多m个公司
		if(oo[i].size()>1){
			st[i].n=oo[i].size()-1;
			st[i].init(oo[i]);
		}
		
	}
	dij(1);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)solve();
    return 0;
}
/*
 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
*/

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 30256kb

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: 106ms
memory: 35704kb

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:

1000110011110111110010100001010100100101000000
1100010010111011011011000000011000001100001000
1000000000000000000000000000000000000000000000
1011010000000010000100010011000100000000000010
1000000000000000000000101000010000001001000001
1111111111111111111111111111111111111111111
101010000000000000010...

result:

wrong answer 6th lines differ - expected: '1001100010110000100001100000000011001110110', found: '1111111111111111111111111111111111111111111'