QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#707808 | #9431. The Quest for El Dorado | chenjue | WA | 114ms | 31696kb | C++20 | 2.4kb | 2024-11-03 17:36:40 | 2024-11-03 17:36:40 |
Judging History
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()-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;
}
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);
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: 100
Accepted
time: 0ms
memory: 28320kb
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: 114ms
memory: 31696kb
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 1001110110110000100101100000100011011111110 101010000000000000010...
result:
wrong answer 6th lines differ - expected: '1001100010110000100001100000000011001110110', found: '1001110110110000100101100000100011011111110'