QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#691217#9431. The Quest for El DoradoEvanRE 0ms3772kbC++203.0kb2024-10-31 10:26:582024-10-31 10:27:01

Judging History

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

  • [2024-10-31 10:27:01]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3772kb
  • [2024-10-31 10:26:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define tp tuple<int,int,int>
struct ST {
    const int n, k;
    vector<vector<int>> Max;
    ST(int n) : n(n), k(__lg(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        //printf("@%d %d\n",l,r);
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        //printf("*%d\n", Max[0][0]);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
};
void solve()
{
    int n,m,k;
    int i,j,u,v,c,l,r;
    scanf("%d %d %d",&n,&m,&k);
    vector<tp> s[n+10];
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&u,&v,&c,&l);
        s[u].push_back({v,c,l});
        s[v].push_back({u,c,l});
    }
    vector<pair<int,int>> t(k+10);
    vector<pair<int,int>> st[m+10];
    vector<int> vis(n+10);
    for(i=1;i<=k;i++)
    {
        scanf("%d %d",&u,&v);
        t[i]={u,v};
        st[u].push_back({v,i});
    }
    vector<ST*> St(m + 10, nullptr);
    for(i=1;i<=m;i++)
    {
        if(st[i].size())
        {
            St[i]=new ST(st[i].size());
            for(j=0;j<st[i].size();j++)
            {
                St[i]->Max[0][j+1]=st[i][j].first;
            }
            St[i]->init();
        }
    }

    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
    pq.push({1,0,1});
    while(!pq.empty())
    {
        tp o=pq.top();pq.pop();
        int x=get<0>(o),y=get<1>(o),z=get<2>(o);
        if(vis[z]){continue;}
        vis[z]=1;
        for(i=0;i<s[z].size();i++)
        {
            if(vis[get<0>(s[z][i])]){continue;}
            int xx=get<0>(s[z][i]),yy=get<1>(s[z][i]),zz=get<2>(s[z][i]);
            if(t[x].first==yy&&y+zz<=t[x].second)
            {
                pq.push({x,y+zz,xx});
                continue;
            }
            else
            {
                if(st[yy][st[yy].size()-1].second<=x){continue;}
                l=0;r=st[yy].size()-1;
                
                while(l<r)
                {
                    int mid=(l+r)/2;
                    if(st[yy][mid].second<x+1){l=mid+1;}
                    else{r=mid-1;}
                }
                //printf("!%d %d\n",l,r);
                r=st[yy].size()-1;
                if(St[yy]->getMax(l+1,r+1)<zz){continue;}
                while(l!=r)
                {
                    int mid=(l+r)/2;
                    if(St[yy]->getMax(l+1,mid+1)>=zz){r=mid;}
                    else{l=mid+1;}
                }
                pq.push({st[yy][l].second,zz,xx});
            }
        }
    }
    for(i=1;i<=n;i++){printf("%d",vis[i]);}
    printf("\n");
}

int main()
{
    int tt;
    scanf("%d",&tt);
    while(tt--){solve();}
}

詳細信息

Test #1:

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

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
Runtime Error

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:


result: