QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#707792 | #9431. The Quest for El Dorado | chenjue | RE | 0ms | 0kb | C++20 | 2.4kb | 2024-11-03 17:33:18 | 2024-11-03 17:33:18 |
answer
#include<bits/stdc++.h>
using namespace std;
#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++;
}
int dis[N];
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()-1;
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;
}
int cc[N];
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){
cin>>cc[i]>>dis[i];
oo[cc[i]].push_back({i,dis[i]});
}
rep(i,1,m){//最多m个公司
if(oo[i].size()>1){
st[i].n=oo[i].size()-1;
st[i].init(oo[i]);
}
}
dij(1);
clear();
}
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: 0
Runtime Error
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