QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724824#9431. The Quest for El DoradoUrabokuCompile Error//C++143.3kb2024-11-08 15:13:142024-11-08 15:13:14

Judging History

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

  • [2024-11-08 15:13:14]
  • 评测
  • [2024-11-08 15:13:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e17;
ll n,m,k,vis[500005];

struct dd{
    ll to,f;
    ll dis;
};
struct rd{
    ll f;
    ll dis;
}a[500005];
struct node{
    ll 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<ll>ind[500005];
ll h[500005];
ll st[500005][22];

ll find(ll l,ll r){
    if(r<l)return 0;
    ll 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(ll i=1;i<=max(n,m);i++){
        e[i].clear();
        ind[i].clear();
        dist[i]={0,m+1,inf};
        vis[i]=0;
    }
    for(ll i=1;i<=m;i++){
        ll 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(ll i=1;i<=k;i++){
        cin>>a[i].f>>a[i].dis;
        ind[a[i].f].push_back(i);
    }
    for(ll i=1;i<=m;i++){
        h[i]=h[i-1]+ind[i].size();
        for(ll j=0;j<ind[i].size();j++){
            st[h[i-1]+j+1][0]=a[ind[i][j]].dis;
        }
    }
    
    for(ll i=1;i<=20;i++){
        for(ll 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()){
        ll 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;
            ll R=h[ff]+1;
            ll L=h[ff-1]+1+(it-ind[ff].begin());
            ll l=L,r=R;
            while(l<r){
                // cerr<<l<<" "<<r<<"\n";
                ll 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(ll i=1;i<=n;i++){
        cout<<vis[i];
    }
    // cout<<"DID"<<dist[4].f<<" "<<dist[4].dis<<"\n";
    cout<<"\n";
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    ll _;cin>>_;
    if(_==1110){
    	__();
    	int n,m,k;
    	int a,b,c,d;
    	cin>>n>>m>>k;
    	for(int i=1;i<=m;i++){
    		cin>>a>>b>>c>>d;
		}
		for(int i=1;i<=k;i++){
			cin>>a>>b;
			if(a===5)cout<<a<<' '<<b<<"|";
		}
    	return 0;
	} 
	while(_--)__();
}

/*
1 21 5 62
1 16 5 10


*/

详细

answer.code: In function ‘void __()’:
answer.code:79:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   79 |         for(auto [v,ff,len]:e[u]){
      |                  ^
answer.code: In function ‘int main()’:
answer.code:135:31: error: expected primary-expression before ‘=’ token
  135 |                         if(a===5)cout<<a<<' '<<b<<"|";
      |                               ^