QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723075#9431. The Quest for El DoradoAlascoWA 80ms40028kbC++143.1kb2024-11-07 21:06:552024-11-07 21:06:55

Judging History

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

  • [2024-11-07 21:06:55]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:40028kb
  • [2024-11-07 21:06:55]
  • 提交

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'