QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#723075 | #9431. The Quest for El Dorado | Alasco | WA | 80ms | 40028kb | C++14 | 3.1kb | 2024-11-07 21:06:55 | 2024-11-07 21:06:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e17;
int n,m,k,vis[500005];
struct dd{
int to,f;
ll dis;
};
struct rd{
int f;
ll dis;
}a[500005];
struct node{
int id,f;
ll dis;
bool operator<(const node y)const{
if(f!=y.f)return f>y.f;
return dis>y.dis;
}
}dist[500005];
vector<dd>e[500005];
vector<int>ind[500005];
int h[500005];
ll st[500005][22];
ll find(int l,int r){
if(r<l)return 0;
int t=0;
while((1<<t)<=(r-l+1)){
t++;
}
t--;
return max(st[l][t],st[r-(1<<t)+1][t]);
}
void __(){
cin>>n>>m>>k;
for(int i=1;i<=max(n,m);i++){
e[i].clear();
ind[i].clear();
dist[i]={0,m+1,inf};
vis[i]=0;
}
for(int i=1;i<=m;i++){
int u,v,c;
ll l;
cin>>u>>v>>c>>l;
e[u].push_back({v,c,l});
e[v].push_back({u,c,l});
}
for(int i=1;i<=k;i++){
cin>>a[i].f>>a[i].dis;
ind[a[i].f].push_back(i);
}
for(int i=1;i<=m;i++){
h[i]=h[i-1]+ind[i].size();
for(int j=0;j<ind[i].size();j++){
st[h[i-1]+j+1][0]=a[ind[i][j]].dis;
}
}
for(int i=1;i<=20;i++){
for(int j=1;j+(1<<(i-1))<=n;j++){
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
priority_queue<node>q;
dist[1]={1,0,0};
q.push(dist[1]);
while(!q.empty()){
int u=q.top().id,f=q.top().f;
ll dis=q.top().dis;
// cerr<<"u"<<u<<"\n";
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,ff,len]:e[u]){
// cerr<<"v"<<v<<"\n";
if(a[f].f==ff&&a[f].dis>=dis+len){
node tmp=node{v,f,dis+len};
if(dist[v]<tmp){
dist[v]=tmp;
q.push(dist[v]);
}
continue;
}
auto it=lower_bound(ind[ff].begin(),ind[ff].end(),f+1);
if(it==ind[ff].end())continue;
int R=h[ff]+1;
int L=h[ff-1]+1+(it-ind[ff].begin());
int l=L,r=R;
while(l<r){
// cerr<<l<<" "<<r<<"\n";
int mid=l+r>>1;
// cerr<<"LR"<<L<<" "<<mid<<" "<<find(L,mid)<<"\n";
if(find(L,mid)>=len){
r=mid;
}else{
l=mid+1;
}
}
if(l>=R){
continue;
}
// cerr<<l<<" "<<h[ff-1]<<" "<<ind[ff][l-h[ff-1]-1]<<"\n";
assert(a[ind[ff][l-h[ff-1]-1]].f==ff);
node tmp=node{v,ind[ff][l-h[ff-1]-1],len};
if(dist[v]<tmp){
dist[v]=tmp;
q.push(dist[v]);
}
}
}
for(int i=1;i<=n;i++){
cout<<vis[i];
}
// cout<<"DID"<<dist[4].f<<" "<<dist[4].dis<<"\n";
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int _;cin>>_;while(_--)__();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32464kb
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: 80ms
memory: 40028kb
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 1000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
wrong answer 2nd lines differ - expected: '1100010010111011011011000000011000001100001000', found: '1000000000000000000000000000000000000000000000'