QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#585533	#9260. Raiffeisenbank Logistics	ucup-team3474^#	TL	1120ms	86444kb	C++20	2.2kb	2024-09-23 21:09:01	2024-09-23 21:09:01

Judging History

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

[2024-09-23 21:09:01]
评测

测评结果：TL
用时：1120ms
内存：86444kb

查看

[2024-09-23 21:09:01]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

typedef struct{
    int to,val,w;
}Node;

vector<Node> e[N];
int q[N];

vector<int> ee[N];

vector<int> mp[N];


void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear(),mp[i].clear(),ee[i].clear();
    // mp.clear();
    deque<PII> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w,0});
        e[v].push_back({u,w,1});
        ee[u].push_back(w);
        ee[v].push_back(w);

    }
    ee[1].push_back(-1);
    for(int i=1;i<=n;i++){
        sort(ee[i].begin(),ee[i].end());
        ee[i].erase(unique(ee[i].begin(),ee[i].end()),ee[i].end());
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=e[i].size();j++) mp[i].push_back(1e9);
    }
    mp[1][0]=0;
    q.push_back({1,-1});
    while(q.size()){
        PII t=q.front();
        q.pop_front();
        int ts=lower_bound(ee[t.first].begin(),ee[t.first].end(),t.second)-ee[t.first].begin();
        
        // cout<<t.first<<" "<<t.second<<" "<<mp[t.first][t.second]<<endl;
        for(auto [to,val,w]:e[t.first]){
            if(val<=t.second) continue;
            if(w==0){
                PII tt={to,val};
                int tts=lower_bound(ee[tt.first].begin(),ee[tt.first].end(),tt.second)-ee[tt.first].begin();
                // if(mp.count(tt)) continue;
                if(mp[tt.first][tts]>mp[t.first][ts]){
                mp[tt.first][tts]=mp[t.first][ts];
                q.push_front(tt);
                }
            }else{
                PII tt={to,val};
                int tts=lower_bound(ee[tt.first].begin(),ee[tt.first].end(),tt.second)-ee[tt.first].begin();
                if(mp[tt.first][tts]>mp[t.first][ts]+1){
                mp[tt.first][tts]=mp[t.first][ts]+1;
                q.push_back(tt);
                }
            }
        }
    }
    int ans=1e9+8;
    for(auto v:mp[n]){
        ans=min(v,ans);
    }
    if(ans>1e8) cout<<-1<<"\n";
    else cout<<ans<<"\n";

}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3584kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3864kb

input:

output:

-1
1

result:

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

Test #3:

score: 0

Accepted

time: 2ms

memory: 3792kb

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

input:

1
2 1
1 2 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 3ms

memory: 3524kb

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: 4ms

memory: 3584kb

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: 3ms

memory: 3636kb

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: 3ms

memory: 3676kb

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: 3ms

memory: 3572kb

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: 4ms

memory: 3572kb

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: 0ms

memory: 3616kb

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: 4ms

memory: 3584kb

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: 5ms

memory: 3580kb

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: 5ms

memory: 3584kb

input:

output:

result:

ok 1000 numbers

Test #15:

score: 0

Accepted

time: 5ms

memory: 3580kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 0

Accepted

time: 6ms

memory: 3620kb

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: 7ms

memory: 3848kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 0

Accepted

time: 8ms

memory: 3532kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 0

Accepted

time: 9ms

memory: 3688kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 0

Accepted

time: 13ms

memory: 3588kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 0

Accepted

time: 14ms

memory: 3808kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 0

Accepted

time: 19ms

memory: 3580kb

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: 47ms

memory: 3592kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 0

Accepted

time: 69ms

memory: 3680kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 0

Accepted

time: 82ms

memory: 3704kb

input:

output:

result:

ok 1000 numbers

Test #26:

score: 0

Accepted

time: 185ms

memory: 3636kb

input:

output:

result:

ok 1000 numbers

Test #27:

score: 0

Accepted

time: 803ms

memory: 3640kb

input:

output:

result:

ok 1000 numbers

Test #28:

score: 0

Accepted

time: 1120ms

memory: 3652kb

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: 61ms

memory: 3828kb

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: 65ms

memory: 3776kb

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: 69ms

memory: 3768kb

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: 80ms

memory: 3664kb

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: 75ms

memory: 3840kb

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: 0

Accepted

time: 295ms

memory: 12160kb

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:

result:

ok 5 number(s): "1 0 2 0 0"

Test #35:

score: 0

Accepted

time: 288ms

memory: 12124kb

input:

5
10000 100000
400 1662 499032381
6939 2059 486853387
8062 4311 263485029
6906 9144 898349721
1374 9791 287537913
1401 2514 179426639
3206 356 654913984
955 4491 102066327
3824 2238 428099250
5030 4171 796495242
3176 8123 228296196
1660 5633 794625946
4996 4363 891788658
4221 4267 717537153
5092 647...

output:

result:

ok 5 number(s): "1 0 2 1 1"

Test #36:

score: 0

Accepted

time: 311ms

memory: 12360kb

input:

5
10000 100000
9526 8284 30390295
2776 8832 185094918
939 7505 922941741
5631 7025 869203187
8618 8178 304297509
4573 6637 697002478
7831 8738 160865264
8640 1154 975091136
3872 1182 637499754
9369 8403 47264467
6368 2555 483838225
7177 4894 244976652
9845 1265 564379654
2955 1436 118973925
3645 199...

output:

result:

ok 5 number(s): "0 1 1 0 1"

Test #37:

score: 0

Accepted

time: 216ms

memory: 43516kb

input:

1
100000 500000
34635 46033 243840177
89991 69694 442882506
19968 21610 887963959
59100 4326 518891263
32030 66602 905457084
6365 4377 378500516
35716 52072 375354442
83763 63671 748057938
90167 71718 314322061
20985 57673 399305781
33422 9344 54429249
8621 10927 88073233
24414 18967 895092185
91512...

output:

-1

result:

ok 1 number(s): "-1"

Test #38:

score: 0

Accepted

time: 214ms

memory: 43248kb

input:

1
100000 500000
15188 94877 126956305
36064 18948 613736176
54124 38302 322768646
61948 64766 801195445
69649 93035 698032982
45412 52100 455948433
23657 16312 543752460
82338 71180 928014228
84388 81926 336635918
20855 4689 124954834
75713 19615 821948475
70517 69931 455049369
11652 49042 460926915...

output:

-1

result:

ok 1 number(s): "-1"

Test #39:

score: 0

Accepted

time: 260ms

memory: 43220kb

input:

1
100000 500000
52638 76426 305039729
14841 68201 344398357
20983 22290 197764822
54396 25205 378466923
96868 95277 340865776
25674 24014 678620542
87405 89065 712150478
24017 78689 548162006
45905 24838 63982479
20726 94809 705379695
85300 72989 734691893
73629 72040 116992802
66185 79117 26761645
...

output:

-1

result:

ok 1 number(s): "-1"

Test #40:

score: 0

Accepted

time: 343ms

memory: 86340kb

input:

1
500000 500000
59280 54906 439822256
429265 418258 621212182
218147 211795 205467984
164946 71245 957403153
481375 344334 382889209
206719 295309 525844696
195710 220464 534488515
49094 402808 390137503
110467 267533 689219374
466476 328515 301654731
60840 13684 148387915
395867 144861 350257604
45...

output:

-1

result:

ok 1 number(s): "-1"

Test #41:

score: 0

Accepted

time: 308ms

memory: 86428kb

input:

1
500000 500000
339833 103751 322938384
440746 267512 646841660
152303 395783 935239967
467793 107493 239707335
451698 413871 25722003
486981 299927 453549509
483651 484705 407919237
147669 10317 865061089
171984 353549 711533231
233642 318636 882079592
370427 491251 61131333
233571 414266 717233740...

output:

-1

result:

ok 1 number(s): "-1"

Test #42:

score: 0

Accepted

time: 332ms

memory: 86444kb

input:

1
500000 500000
344579 152595 795989104
419522 359869 522728034
86458 79771 810236143
27537 367932 522011518
146214 240305 963522093
426027 80354 530997427
80103 314354 281349959
22052 117827 190241570
266205 163757 438879792
33513 32948 312761349
488526 277329 533683263
360875 473271 379177172
1284...

output:

-1

result:

ok 1 number(s): "-1"

Test #43:

score: -100

Time Limit Exceeded

input:

1
40003 80000
35719 1310 38202
835 12806 47060
3603 7710 11806
14153 3125 43071
4939 15539 4841
33565 14175 16271
20550 10855 10018
32124 23731 12555
1753 13312 56596
25501 38087 44821
7833 1310 37857
29811 1310 31956
1310 26094 31445
1088 1310 31689
7975 26106 41605
3119 1310 33900
1310 30057 37747...