QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#334587	#8232. Yet Another Shortest Path Query	ucup-team134	WA	925ms	484472kb	C++14	6.9kb	2024-02-22 07:00:23	2024-02-22 07:00:24

Judging History

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

[2024-02-22 07:00:24]
评测

测评结果：WA
用时：925ms
内存：484472kb

查看

[2024-02-22 07:00:23]
提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=1e6+10;
const double max_load_cap=0.2;

int inf=1e9;

struct chash{
    const uint64_t C= (ll)(4e18*acos(0))|71;
    ll operator()(ll x)const{return __builtin_bswap64(x*C);}
};

vector<pii>vg[maxn],vout[maxn],vin[maxn];
vector<int>niz,revniz;
unordered_map<int,int,chash>map_out[maxn],map_in[maxn],map_rez[maxn];

int n,m,deg[maxn],pos[maxn],q,rez_qry[maxn];

void init(){

    for(int i=1;i<=n;i++){
        map_out[i].max_load_factor(max_load_cap);
        map_in[i].max_load_factor(max_load_cap);
        map_rez[i].max_load_factor(max_load_cap);

        for(int j=0;j<vout[i].size();j++)map_out[i][vout[i][j].ff]=vout[i][j].ss;
        for(int j=0;j<vin[i].size();j++)map_in[i][vin[i][j].ff]=vin[i][j].ss;

        ///printf("%d %d AAA\n",i,niz[i]);
    }

}

void prek(){

    vector<int>good;
    for(int i=1;i<=n;i++){
        if(deg[i]<=5)good.pb(i);
    }

    niz.pb(0);
    revniz.resize(n+1);
    for(int i=1;i<=n;i++){
        int id=good.back();
        good.pop_back();
        niz.pb(id);
        revniz[id]=niz.size()-1;
        pos[id]=1;

        for(int j=0;j<vg[id].size();j++){
            int id2=vg[id][j].ff;
            if(pos[id2])continue;
            deg[id2]--;
            if(deg[id2]==5)good.pb(id2);
        }

    }

    for(int i=1;i<=n;i++){

        for(int j=0;j<vg[i].size();j++){
            int id=vg[i][j].ff;
            int w=vg[i][j].ss;

            int a=revniz[i];
            int b=revniz[id];

            if(a>b){
                continue;
            }

            vout[a].pb({b,w});
            vin[b].pb({a,w});
        }

    }

}

void update_rez(int a,int b,int w){
    if(a>b)swap(a,b);
    if(map_rez[a].find(b)==map_rez[a].end())map_rez[a][b]=w;
    else{
        int &p=map_rez[a][b];
        p=min(p,w);
    }
}

void go_LR(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vout[i].size();j++){
            int id1=vout[i][j].ff;
            int w1=vout[i][j].ss;

            update_rez(i,id1,w1);

            for(int k=j+1;k<vout[i].size();k++){
                int id2=vout[i][k].ff;
                int w2=vout[i][k].ss;

                update_rez(id1,id2,w1+w2);
            }
        }

    }

}
void go_lrr_llr(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vout[i].size();j++){
            int id1=vout[i][j].ff;
            int w1=vout[i][j].ss;

            for(int k=0;k<vout[i].size();k++){
                int id2=vout[i][k].ff;
                if(id2==id1)continue;
                int w2=vout[i][k].ss;

                for(int p=0;p<vout[id2].size();p++){
                    int id3=vout[id2][p].ff;
                    int w3=vout[id2][p].ss;

                    ///printf("%d %d %d %d AAA\n",i,id1,id2,id3);

                    update_rez(id1,id3,w1+w2+w3);
                }

            }
        }

    }

}

struct qry{
    int a,b,w,id;
}pocqry[maxn];

vector<qry>newqry;

void go_make_k2(){

    for(int i=1;i<=q;i++){

        int a=pocqry[i].a;
        int b=pocqry[i].b;

        qry pom2;
        pom2.id=i;
        pom2.a=a;
        pom2.b=b;
        pom2.w=0;
        newqry.pb(pom2);

        for(int j=0;j<vout[a].size();j++){
            int id=vout[a][j].ff;
            int w=vout[a][j].ss;

            qry pom;
            pom.id=pocqry[i].id;
            pom.w=w;
            pom.a=id;
            pom.b=b;
            ///printf("%d %d EDGE A\n",pom.a,pom.b);
            if(pom.a>pom.b)swap(pom.a,pom.b);
            newqry.pb(pom);
        }
        for(int j=0;j<vout[b].size();j++){
            int id=vout[b][j].ff;
            int w=vout[b][j].ss;

            qry pom;
            pom.id=pocqry[i].id;
            pom.w=w;
            pom.a=a;
            pom.b=id;
            ///printf("%d %d EDGE B\n",pom.a,pom.b);
            if(pom.a>pom.b)swap(pom.a,pom.b);
            newqry.pb(pom);
        }
    }

    /*for(int i=0;i<newqry.size();i++){
        printf("%d %d %d %d NQ\n",newqry[i].a,newqry[i].b,newqry[i].id,newqry[i].w);
    }*/

}
void go_upd_LR_k2(){
    return;
    for(int i=0;i<newqry.size();i++){
        if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end())
            rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
    }
}

void go_RR_k2(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vin[i].size();j++){
            for(int k=0;k<vout[i].size();k++){
                int id1=vin[i][j].ff;
                int id2=vout[i][k].ff;
                int w1=vin[i][j].ss;
                int w2=vout[i][k].ss;

                ///printf("%d %d |");
                update_rez(id1,id2,w1+w2);
            }
        }

    }

    for(int i=0;i<newqry.size();i++){
        if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end())
            rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
    }

}

void go_RL_k2(){

    for(int i=0;i<newqry.size();i++){
        int id=newqry[i].id;
        int a=newqry[i].a;
        int b=newqry[i].b;
        int w=newqry[i].w;

        for(int j=0;j<vout[a].size();j++){
            int id2=vout[a][j].ff;
            int w2=vout[a][j].ss;

            if(map_in[id2].find(b)!=map_in[id2].end())
                rez_qry[id]=min(rez_qry[id],w2+w+map_in[id2][b]);
        }

    }

}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        vg[a].pb({b,w});
        vg[b].pb({a,w});
        deg[a]++;
        deg[b]++;
    }

    prek();
    init();


    go_LR();
    go_lrr_llr();

    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        rez_qry[i]=inf;
        int a,b;
        scanf("%d %d",&a,&b);
        a=revniz[a];
        b=revniz[b];
        if(a>b)swap(a,b);
        pocqry[i].id=i;
        pocqry[i].a=a;
        pocqry[i].b=b;
        pocqry[i].w=0;
    }
    go_make_k2();

    go_upd_LR_k2();
    go_RR_k2();
    go_RL_k2();

    for(int i=1;i<=q;i++){
        int a=pocqry[i].a;
        int b=pocqry[i].b;
        if(map_rez[a].find(b)!=map_rez[a].end())rez_qry[i]=min(rez_qry[i],map_rez[a][b]);
        if(rez_qry[i]==inf)printf("-1\n");
        else printf("%d\n",rez_qry[i]);
    }

    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 103ms

memory: 262940kb

input:

output:

result:

ok 5 number(s): "6 8 3 1 7"

Test #2:

score: 0

Accepted

time: 54ms

memory: 261664kb

input:

output:

3
-1
-1

result:

ok 3 number(s): "3 -1 -1"

Test #3:

score: -100

Wrong Answer

time: 925ms

memory: 484472kb

input:

40005 79608
1 2 70031203
1 3 99924845
1 4 61645659
1 5 9324967
2 3 15761918
3 4 62534796
4 5 35260314
5 2 35948540
6 2 23727405
6 7 83302920
7 3 31010426
7 8 75060393
8 4 94275932
8 9 99663793
9 5 81701979
9 6 439297
10 6 46955645
10 11 89514237
11 7 21257310
11 12 53896253
12 8 67933315
12 13 26161...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 6236th numbers differ - expected: '-1', found: '146724051'