QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718181#9431. The Quest for El DoradotriccsrWA 93ms23532kbC++203.9kb2024-11-06 19:53:482024-11-06 19:53:55

Judging History

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

  • [2024-11-06 19:53:55]
  • 评测
  • 测评结果:WA
  • 用时:93ms
  • 内存:23532kb
  • [2024-11-06 19:53:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
const int N=5e5+11;
typedef long long LL;
const int inf=0x3f3f3f3f;
const LL llinf=1e18;
struct E{
    int to,c;
    LL len;
};
struct H{
    int cnt;
    LL dis;
    int index;
    bool operator<(const H &h)const{
        if(cnt!=h.cnt)return cnt>h.cnt;
        if(dis!=h.dis)return dis>h.dis;
        return index>h.index;
    }
};
class SegmentTree{
    #define ls(x) ((x)<<1)
    #define rs(x) (((x)<<1)|1)
    #define mid ((l+r)>>1)
    int n;
    vector<LL> mx;
    void update(int now){
        mx[now]=max(mx[ls(now)],mx[rs(now)]);
    }
    void build(int l,int r,int now,const vector<LL> & a){
        if(l==r){
            mx[now]=a[l];
            return;
        }
        build(l,mid,ls(now),a);
        build(mid+1,r,rs(now),a);
        update(now);
    }
    int first_geq(int l,int r,int now,int st,int en,LL v){
        if(st<=l&&r<=en){
            if(mx[now]<v)return -1;
            if(l==r)return l;
            if(mx[ls(now)]>=v)return first_geq(l,mid,ls(now),st,en,v);
            return first_geq(mid+1,r,rs(now),st,en,v);
        }
        int ret=-1;
        if(st<=mid){
            ret=first_geq(l,mid,ls(now),st,en,v);
        }
        if(ret==-1&&en>mid){
            ret=first_geq(mid+1,r,rs(now),st,en,v);
        }
        return ret;
    }
public:
    SegmentTree()=default;
    SegmentTree(const vector<LL> &vec):n((int)vec.size()){
        mx.resize(4*n+1);
        build(0,n-1,1,vec);
    }
    int first_geq(int st,LL v){
        if(st>=n)return -1;
        return first_geq(0,n-1,1,st,n-1,v);
    }
    #undef ls
    #undef rs
    #undef mid
};
int n,m,k;
int a[N];
LL b[N];
bool ok[N];
int cnt[N];
LL dis[N];
vector<E> e[N];
vector<int> cp[N];
SegmentTree sgt[N];
int it[N];
void work(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
        e[i].clear();
        ok[i]=false;
        cnt[i]=inf;
        dis[i]=llinf;
    }
    for(int i=1;i<=m;++i){
        cp[i].clear();
        it[i]=0;
    }
    for(int i=1;i<=m;++i){
        int u,v,c;
        LL l;
        cin>>u>>v>>c>>l;
        e[u].emplace_back((E){v,c,l});
        e[v].emplace_back((E){u,c,l});
    }
    for(int i=1;i<=k;++i){
        cin>>a[i]>>b[i];
        cp[a[i]].push_back(i);
    }
    for(int i=1;i<=m;++i){
        if(cp[i].empty())continue;
        vector<LL> dd;
        dd.resize(cp[i].size());
        for(int j=0;j<(int)cp[i].size();++j){
            dd[j]=b[cp[i][j]];
        }
        sgt[i]=SegmentTree(dd);
    }
    priority_queue<H> pq;
    cnt[1]=1;
    dis[1]=0;
    pq.push((H){.cnt=1,.dis=0,.index=1});
    for(int loop=1;loop<=n;++loop){
        while(!pq.empty()&&ok[pq.top().index])pq.pop();
        if(pq.empty())break;
        int now=pq.top().index;
        pq.pop();
        ok[now]=true;
        int nowc=a[cnt[now]];
        for(auto [to,c,len]:e[now]){
            if(ok[to])continue;
            int newcnt=inf;
            LL newdis=llinf;
            if(nowc==c&&dis[now]+len<=b[cnt[now]]){
                newcnt=cnt[now];
                newdis=dis[now]+len;
            }
            else{
                while(it[c]!=(int)cp[c].size()&&cp[c][it[c]]<=cnt[now])++it[c];
                int tmp=sgt[c].first_geq(it[c],len);
                if(tmp!=-1){
                    newcnt=cp[c][tmp];
                    newdis=len;
                }
            }
            if(newcnt<cnt[to]||(newcnt==cnt[to]&&newdis<dis[to])){
                cnt[to]=newcnt;
                dis[to]=newdis;
                pq.emplace((H){cnt[to],dis[to],to});
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(cnt[i]!=inf)printf("1");
        else printf("0");
    }
    printf("\n");
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 22020kb

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: 93ms
memory: 23532kb

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
1001100010110000100001100000000011001110110
101010000000000000010...

result:

wrong answer 18th lines differ - expected: '111111111111111001111111111111111111111111111111', found: '111111111111111111111111111111111111111111111111'