QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#585652	#9260. Raiffeisenbank Logistics	ucup-team3474^#	TL	748ms	117328kb	C++20	2.5kb	2024-09-23 21:40:24	2024-09-23 21:40:24

Judging History

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

[2024-09-23 21:40:24]
评测

测评结果：TL
用时：748ms
内存：117328kb

查看

[2024-09-23 21:40:24]
提交

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,val2;
}Node;

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

vector<int> ee[N];

vector<int> mp[N];
vector<int> tf[N];

void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear(),mp[i].clear(),ee[i].clear(),tf[i].clear();
    // mp.clear();
    deque<array<int,3>> 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),tf[i].push_back(0);
    }
    for(int i=1;i<=n;i++){
        for(auto &[to,val,w,val2]:e[i])
        {
             int tts=lower_bound(ee[to].begin(),ee[to].end(),val)-
             ee[to].begin();
             val2=tts;   

        }
    }
    mp[1][0]=0;
    tf[1][0]=1;
    q.push_back({1,-1,0});
    while(q.size()){
        auto t=q.front();
        q.pop_front();
        int ts=lower_bound(ee[t[0]].begin(),ee[t[0]].end(),t[1])-ee[t[0]].begin();
        // cout<<t[0]<<" "<<t
        // cout<<t[0]<<" "<<t[1]<<" "<<t[2]<<endl;
        for(auto [to,val,w,val2]:e[t[0]]){
            if(val<=t[1]) continue;
            if(w==0){
               array<int,3> tt={to,val,w};
                int tts=val2;
                // if(mp.count(tt)) continue;
                if(mp[tt[0]][tts]>t[2]){
                mp[tt[0]][tts]=t[2];
                tf[tt[0]][tts]=1;
                tt[2]=t[2];
                q.push_front(tt);
                }
            }else{
               array<int,3> tt={to,val,w};
               int tts=val2;
                if(mp[tt[0]][tts]>t[2]+1){
                mp[tt[0]][tts]=t[2]+1;
                tf[tt[0]][tts]=1;
                tt[2]=t[2]+1;
                q.push_front(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: 3620kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3548kb

input:

output:

-1
1

result:

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

Test #3:

score: 0

Accepted

time: 2ms

memory: 3576kb

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

memory: 3808kb

input:

1
2 1
1 2 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 2ms

memory: 3568kb

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

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

memory: 3628kb

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

memory: 3784kb

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

memory: 3816kb

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

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

memory: 3584kb

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

memory: 3632kb

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

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

memory: 3520kb

input:

output:

result:

ok 1000 numbers

Test #15:

score: 0

Accepted

time: 6ms

memory: 3788kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 0

Accepted

time: 7ms

memory: 3852kb

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

memory: 5676kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 0

Accepted

time: 10ms

memory: 3592kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 0

Accepted

time: 10ms

memory: 3620kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 0

Accepted

time: 10ms

memory: 3644kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 0

Accepted

time: 17ms

memory: 3664kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 0

Accepted

time: 18ms

memory: 3652kb

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

memory: 3888kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 0

Accepted

time: 71ms

memory: 3720kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 0

Accepted

time: 86ms

memory: 3724kb

input:

output:

result:

ok 1000 numbers

Test #26:

score: 0

Accepted

time: 153ms

memory: 3616kb

input:

output:

result:

ok 1000 numbers

Test #27:

score: 0

Accepted

time: 511ms

memory: 3700kb

input:

output:

result:

ok 1000 numbers

Test #28:

score: 0

Accepted

time: 748ms

memory: 3704kb

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

memory: 3880kb

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

memory: 3832kb

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

memory: 3792kb

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

memory: 3784kb

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

memory: 3836kb

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

memory: 14964kb

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

memory: 14672kb

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

memory: 14968kb

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

memory: 57256kb

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

memory: 57428kb

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

memory: 57432kb

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

memory: 117088kb

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

memory: 117316kb

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

memory: 117328kb

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