QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#563629	#9260. Raiffeisenbank Logistics	PhantomThreshold^#	TL	753ms	4132kb	C++20	2.6kb	2024-09-14 14:33:06	2024-09-14 14:33:07

Judging History

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

[2024-09-14 14:33:07]
评测

测评结果：TL
用时：753ms
内存：4132kb

查看

[2024-09-14 14:33:06]
提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1510000;

int n,m;
int tot;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int Tcase; cin>>Tcase;
    while(Tcase--)
    {
        vector< vector< pair<int,int> > >E;
        vector< vector<int> >V;
        vector< tuple<int,int,int> >ei;

        cin>>n>>m;
        V.resize(n+5);
        for(int i=1;i<=m;i++)
        {
            int x,y,t; cin>>x>>y>>t;
            ei.emplace_back(x,y,t);
            V[x].push_back(t),V[y].push_back(t);
            V[x].push_back(t+1),V[y].push_back(t+1);
        }
        
        if(V[1].empty())
        {
            cout<<-1<<'\n';
            continue;
        }

        tot=0;
        map< pair<int,int>,int>mp;
        for(int i=1;i<=n;i++)
        {
            sort(V[i].begin(),V[i].end());
            for(auto t:V[i])
            {
                auto temp= make_pair(i,t);
                if(mp.count(temp)==0) 
                {
                    mp[temp]=++tot;
            //        cerr<<i<<' '<<t<<' '<<tot<<endl;
                }
            }
        }
        E.resize(tot+5);
        for(int i=1;i<=n;i++)
        {
            int las=-1;
            for(auto t:V[i])
            {
                if(las!=-1 && las!=t)
                {
                    int u= mp[make_pair(i,las)], v=mp[make_pair(i,t)];
                    E[u].emplace_back(0,v);
                }
                las=t;
            }
        }
        for(auto [x,y,t]:ei)
        {
            E[ mp[make_pair(x,t)] ].emplace_back(0, mp[make_pair(y,t+1)] );
            E[ mp[make_pair(y,t)] ].emplace_back(1, mp[make_pair(x,t+1)] );
        }
        
        const int inf = 1e9;
        vector<int>dis(tot+5);
        for(int i=1;i<=tot;i++) dis[i]=inf;
        deque< pair<int,int> >q;
        dis[1]=0; q.push_back( make_pair(1,0) );
        while(!q.empty())
        {
            const auto [x,dx]=q.front(); q.pop_front();
            if(dx!=dis[x]) continue;
            for(auto [c,y]:E[x])
            {
                if(dis[y]>dx+c)
                {
                    dis[y]=dx+c;
                    if( c==0 ) q.push_front( make_pair(y,dis[y]) );
                    else q.push_back( make_pair(y,dis[y]) );
                }
            }
        }
        int ans=inf;
        for(auto t:V[n])
        {
            int u= mp[make_pair(n,t)];
            ans=min(ans,dis[u]);
        }
        if(ans==inf) ans=-1;
        cout<<ans<<'\n';
    }

    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3820kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

output:

-1
1

result:

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

Test #3:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

8
2 1
1 2 1
2 1
2 1 1
2 1
1 1 1
2 1
2 2 1
2 1
1 2 1000000000
2 1
2 1 1000000000
2 1
1 1 1000000000
2 1
2 2 1000000000

output:

0
1
-1
-1
0
1
-1
-1

result:

ok 8 numbers

Test #4:

score: 0

Accepted

time: 0ms

memory: 3820kb

input:

1
2 1
1 2 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 5ms

memory: 3652kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-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
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
0
-1
1
-1
-1
-...

result:

ok 1000 numbers

Test #6:

score: 0

Accepted

time: 6ms

memory: 3576kb

input:

output:

-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
0
0
-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
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
-1
-1
1
0
0
1
-1
-1
-1
-1
1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #7:

score: 0

Accepted

time: 7ms

memory: 3648kb

input:

output:

0
1
-1
2
-1
-1
1
0
0
-1
1
-1
0
-1
1
-1
-1
-1
-1
1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
1
2
-1
1
-1
-1
2
1
-1
-1
-1
1
-1
1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
0
1
1
-1
1
-1
-1
1
2
-1
-1
1
-1
-1
0
-1
0
-1
0
-1
-1
-1
-1
1
-1
0
-1
0
-1
1
0
0
-1
-1
-1
-1
-1
1
1
-1
2
-1
-1
0
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
0
-1
1
-1
0
-1
0
-...

result:

ok 1000 numbers

Test #8:

score: 0

Accepted

time: 8ms

memory: 3584kb

input:

output:

2
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
2
-1
0
-1
-1
-1
-1
0
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
2
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
...

result:

ok 1000 numbers

Test #9:

score: 0

Accepted

time: 9ms

memory: 3872kb

input:

output:

1
-1
-1
-1
0
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
2
0
0
-1
1
-1
-1
-1
0
-1
3
-1
-1
1
0
-1
-1
-1
-1
0
-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
0
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
0
-1
2
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
...

result:

ok 1000 numbers

Test #10:

score: 0

Accepted

time: 9ms

memory: 3596kb

input:

1000
10 10
10 10 268155137
5 10 540061009
1 10 110627680
1 4 533692575
3 5 10438095
6 7 730490278
6 2 985939776
8 10 500039201
1 9 185735931
4 2 729538420
10 10
8 1 326383784
5 3 726281100
4 6 279162422
4 4 243297959
1 2 984988531
3 10 856724546
2 4 627158366
4 5 880246199
9 1 675003875
7 7 76366643...

output:

0
-1
-1
-1
-1
0
-1
2
1
-1
2
-1
-1
-1
-1
1
-1
1
-1
0
-1
2
1
2
-1
-1
0
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
0
-1
-1
-1
-1
-1
1
1
1
-1
0
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
0
-1
-1
-1
0
1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
0
-1...

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 8ms

memory: 3640kb

input:

output:

-1
1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
0
1
-1
0
-1
-1
-1
-1
0
0
1
1
-1
1
-1
-1
-1
0
-1
0
-1
-1
-1
1
-1
-1
1
-1
-1
1
0
-1
-1
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
0
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
0
1
1
0
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
0
-1
0
...

result:

ok 1000 numbers

Test #12:

score: 0

Accepted

time: 11ms

memory: 3540kb

input:

output:

-1
-1
2
0
0
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
0
-1
-1
2
-1
-1
-1
-1
1
-1
0
0
1
1
1
1
1
0
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
1
-1
2
0
2
1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
0
1
-1
0
2
0
-1
0
-1
2
1
-1
0
-1
-1
2
-1
-1
-1
-1
2
-1
1
-1
-1
0
0
-1
0
0
2
-1
0
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
1...

result:

ok 1000 numbers

Test #13:

score: 0

Accepted

time: 9ms

memory: 3844kb

input:

output:

-1
0
-1
0
0
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
-1
0
-1
1
-1
-1
-1
0
-1
-1
-1
2
1
-1
-1
1
-1
-1
2
-1
0
1
1
-1
-1
-1
-1
-1
0
1
1
-1
-1
2
-1
-1
2
2
0
1
-1
0
-1
-1
0
1
-1
1
-1
0
-1
-1
0
1
2
0
0
-1
1
-1
1
0
-1
-1
-1
-1
0
0
-1
-1
0
2
1
0
1
-1
-1
2
1
1
0
0
2
2
1
1
-1
0
0
0
1
0
-1
1
-1
1
0
0
-1
-1
-1
-1
1
-1
-1...

result:

ok 1000 numbers

Test #14:

score: 0

Accepted

time: 20ms

memory: 3656kb

input:

output:

result:

ok 1000 numbers

Test #15:

score: 0

Accepted

time: 19ms

memory: 3580kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 0

Accepted

time: 23ms

memory: 3660kb

input:

1000
10 20
9 8 326353980
1 10 321178299
4 8 970616710
4 9 550923176
8 9 682488932
10 6 752852755
5 10 399703822
10 10 207683413
7 9 84451826
7 8 820433227
7 5 97884128
6 7 1405220
1 5 287655030
8 9 868446569
4 1 421832399
9 4 913601101
2 9 361785960
9 3 425625400
3 9 1891923
8 1 112588430
10 20
6 9 ...

output:

result:

ok 1000 numbers

Test #17:

score: 0

Accepted

time: 16ms

memory: 3660kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 0

Accepted

time: 21ms

memory: 3600kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 0

Accepted

time: 27ms

memory: 3564kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 0

Accepted

time: 44ms

memory: 3884kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 0

Accepted

time: 63ms

memory: 3728kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 0

Accepted

time: 65ms

memory: 3908kb

input:

1000
10 50
2 2 954153759
1 3 283444488
8 10 897162377
6 2 701352810
5 8 872948443
6 10 320895294
10 9 697730752
5 4 375661090
3 4 673334850
6 9 215515206
10 7 977251708
6 1 888046403
5 2 292147356
9 9 840382008
3 10 430429980
6 8 921004331
4 10 298467905
7 1 160104863
10 3 444341972
10 4 653051505
9...

output:

result:

ok 1000 numbers

Test #23:

score: 0

Accepted

time: 101ms

memory: 3612kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 0

Accepted

time: 130ms

memory: 3880kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 0

Accepted

time: 148ms

memory: 3640kb

input:

output:

result:

ok 1000 numbers

Test #26:

score: 0

Accepted

time: 224ms

memory: 3632kb

input:

output:

result:

ok 1000 numbers

Test #27:

score: 0

Accepted

time: 530ms

memory: 3804kb

input:

output:

result:

ok 1000 numbers

Test #28:

score: 0

Accepted

time: 753ms

memory: 4132kb

input:

1000
10 500
8 9 67526824
5 4 559064935
10 5 4911091
10 1 665435421
10 9 676899734
7 1 937378183
8 5 573246092
4 7 989380774
4 6 200810178
7 1 416005093
8 8 742684190
1 10 268750539
2 5 718281171
1 8 934536165
1 5 814664163
2 7 237449715
2 1 203051765
6 7 306356562
10 3 428234841
3 1 760994730
10 2 7...

output:

result:

ok 1000 numbers

Test #29:

score: 0

Accepted

time: 376ms

memory: 3760kb

input:

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:

ok 1000 numbers

Test #30:

score: 0

Accepted

time: 441ms

memory: 3764kb

input:

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:

ok 1000 numbers

Test #31:

score: 0

Accepted

time: 468ms

memory: 3796kb

input:

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:

ok 1000 numbers

Test #32:

score: 0

Accepted

time: 508ms

memory: 3808kb

input:

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
-1...

result:

ok 1000 numbers

Test #33:

score: 0

Accepted

time: 522ms

memory: 3888kb

input:

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
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000 numbers

Test #34:

score: -100

Time Limit Exceeded

input:

5
10000 100000
16 3559 468695643
7133 1854 827377604
2253 8986 212718926
3378 8735 205907497
3784 3272 98819139
5961 1839 898392689
4722 371 109250145
8884 4871 589883888
7498 9813 70864069
9475 6017 175126069
2932 4557 863780576
7285 6064 122334857
5448 5260 360605203
2995 6162 705458859
9806 2832 ...

output: