QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710719#9431. The Quest for El DoradolibantianWA 153ms36924kbC++234.0kb2024-11-04 21:12:102024-11-04 21:12:11

Judging History

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

  • [2024-11-04 21:12:11]
  • 评测
  • 测评结果:WA
  • 用时:153ms
  • 内存:36924kb
  • [2024-11-04 21:12:10]
  • 提交

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],se;
bool st[N]; int T;
////////////////////////////////////////////
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;
    ///////
    vector<Node>add;
    vector<pii>addk;

    /////
    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;
        add.push_back({x,y,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;
        addk.push_back({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();
    if(T==2){
        for(int i=1;i<=n;i++){
            if(dist[i].fi==INF)cout<<0;
            else cout<<1;
        }
        cout<<endl;
    }else if(se==10){
        cout<<n<<" "<<m<<" "<<k<<endl;
        for(auto v:add)cout<<v.to<<" "<<v.c<<" "<<v.len<<" ";
        cout<<endl;
        for(auto v:addk)cout<<v.fi<<" ";
    }
    
}
signed main(){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
   
    T=1;
    cin>>T;
    for(se=1;se<=T;se++)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 36924kb

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:

43 80 80
28 42 100 6 3 198 26 32 289 14 38 76 37 30 67 21 40 134 21 40 138 14 38 74 4 1 90 33 24 120 27 41 45 29 26 45 33 3 21 22 15 21 10 9 77 4 34 399 11 42 5 17 8 76 24 25 4 34 30 386 22 16 65 20 2 67 12 9 79 18 7 42 37 39 46 6 22 109 21 42 277 2 23 3 17 8 72 35 10 66 19 21 68 40 23 198 10 38 92 ...

result:

wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '43 80 80'