QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710694#9431. The Quest for El DoradolibantianWA 153ms43788kbC++233.7kb2024-11-04 21:03:442024-11-04 21:03:44

Judging History

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

  • [2024-11-04 21:03:44]
  • 评测
  • 测评结果:WA
  • 用时:153ms
  • 内存:43788kb
  • [2024-11-04 21:03:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pir pair<pii,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
struct Node
{
    int to,c,len;
};
const int N=500010;
vector<Node>g[N];
set<array<int,3>> s[N];
pii dist[N];
int l[N],r[N],a[N],t[N],ft[N];
bool st[N];
////////////////////////////////////////////
struct node
{
    int l, r;
    int v;  // 区间[l, r]中的最大值
}tr[N * 4];

void pushup(int u)  // 由子节点的信息,来计算父节点的信息
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) {
        tr[u].v=a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点,已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}
////////////////////////////////////////
void dij(){
    dist[1].fi=0;
    priority_queue<pir,vector<pir>,greater<pir>>q;
    q.push({dist[1],1});
    while(q.size()){
        int u=q.top().se;
        q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto ne:g[u]){
            int v=ne.to;
            int c=ne.c;
            int len=ne.len;
            if(t[dist[u].fi]==c&&len<=dist[u].se){
                pii p={dist[u].fi,dist[u].se-len};
                if(p<dist[v]){
                    dist[v]=p;
                    q.push({dist[v],v});
                }

                continue;
            }
            if(s[c].empty())continue;
            auto it=s[c].lower_bound({dist[u].fi,INF,INF});
            if(it==s[c].end())continue;
            int L=l[c]+(*it)[1],R=r[c];
            if(query(1,L,R)<len)continue;
            {
                int l=L,r=R;

                while(l<r){
                    int mid=l+r>>1;
                    if(query(1,L,mid)>=len)r=mid;
                    else l=mid+1;
                }
                pii p={ft[r],query(1,L,r)-len};
                if(p<dist[v]){
                    dist[v]=p;
                    q.push({dist[v],v});
                }
            }
        }

    }
}
////////////////////////////////////////
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        dist[i].fi=INF;
        st[i]=false;
        g[i].clear();
        
    }
    for(int i=1;i<=m;i++){
        s[i].clear();
        l[i]=r[i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,c,len;
        cin>>x>>y>>c>>len;
        g[x].push_back({y,c,len});
        g[y].push_back({x,c,len});
    }
    for(int i=1;i<=k;i++){
        int c,len;
        cin>>c>>len;
        s[c].insert({i,(int)s[c].size(),len});
        t[i]=c;
    }
    int len=0;
    for(int i=1;i<=m;i++){
        if(s[i].empty())continue;
        l[i]=len+1;
        r[i]=len+s[i].size();
        for(auto v:s[i]){
            int x=v[2];
            a[++len]=x;
            ft[len]=v[0];
        }
    }
    build(1,1,len);
    dij();
    for(int i=1;i<=n;i++){
        if(dist[i].fi==INF)cout<<0;
        else cout<<1;
    }
    cout<<endl;
}
signed main(){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int T;
    T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 38416kb

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: 153ms
memory: 43788kb

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 10th lines differ - expected: '1001100111010000100000000110100000010000001', found: '1001100110010000100000000110100000010000001'