QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#76001 | #5458. Shortest Path Query | upsolveupsolve | AC ✓ | 778ms | 244592kb | C++20 | 2.3kb | 2023-02-07 02:27:34 | 2023-02-07 02:27:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=50005,INF=1<<30;
vector<array<int,3>> rG[MAX];
vector<pair<ll,ll>> totsu[MAX];
vector<array<ll,3>> que[MAX];
ll ans[MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int N,M;cin>>N>>M;
for(int i=0;i<M;i++){
int a,b;cin>>a>>b;a--;b--;
int x;cin>>x;
if(x==0) rG[b].push_back({a,1,0});
else rG[b].push_back({a,0,1});
}
int Q;cin>>Q;
for(int q=0;q<Q;q++){
int a,b,x;cin>>a>>b>>x;x--;
que[x].push_back({a,b,q});
}
totsu[0].push_back(mp(0,0));
for(int t=0;t<N;t++){
vector<pair<ll,ll>> S;
for(auto [from,aa,bb]:rG[t]){
vector<pair<ll,ll>> T;
for(auto [a,b]:totsu[from]) T.push_back(mp(a+aa,b+bb));
vector<pair<ll,ll>> nex;
merge(all(S),all(T),back_inserter(nex));
S.clear();
for(auto [a,b]:nex){
while(si(S)>=2){
auto [x,y]=S[si(S)-2];
auto [p,q]=S[si(S)-1];
if((y-q)*(p-a)>=(x-p)*(q-b)) S.pop_back();
else break;
}
S.push_back(mp(a,b));
}
}
if(t==0) S=totsu[t];
for(auto [a,b,id]:que[t]){
ll l=-1,r=si(S);
while(r-l>2){
ll m1=(l+l+r)/3,m2=(l+r+r)/3;
ll x=a*S[m1].fi+b*S[m1].se,y=a*S[m2].fi+b*S[m2].se;
if(x<y) r=m2;
else l=m1;
}
ll m=(l+r)/2;
ans[id]=a*S[m].fi+b*S[m].se;
}
totsu[t]=S;
if(t>=1000) totsu[t-1000].clear();
}
for(int q=0;q<Q;q++) cout<<ans[q]<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 6888kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: 0
Accepted
time: 105ms
memory: 19288kb
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...
output:
164602050 208733870 228180204 248456409 87574800 16685198 46684062 64713954 46949896 240633535 94777502 83016099 259833741 167838804 214963500 147454419 111021650 80187604 184782450 78138570 86528820 203553394 188095596 202049239 290053220 172790198 168899028 97757186 96431009 266952297 164349486 26...
result:
ok 50000 numbers
Test #3:
score: 0
Accepted
time: 151ms
memory: 37620kb
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 0 6 7 1 7 8 0 8 9 0 9 10 1 10 11 1 11 12 1 12 13 1 13 14 0 14 15 1 15 16 1 16 17 1 17 18 0 18 19 0 19 20 1 20 21 1 21 22 1 22 23 0 23 24 0 24 25 1 25 26 1 26 27 0 27 28 0 28 29 1 29 30 0 30 31 1 31 32 1 32 33 1 33 34 0 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...
output:
100196045 31414400 96903432 4429901 131353947 100466556 96621590 116427456 86564241 138309577 111227766 96757449 98894394 113624940 103437724 32090169 118889544 27383865 145395709 52415186 44958306 178247166 101837390 123750212 66411806 29005113 61920301 53700468 83473964 101048973 24035890 82224385...
result:
ok 50000 numbers
Test #4:
score: 0
Accepted
time: 187ms
memory: 49320kb
input:
50000 100000 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 0 8 9 0 9 10 0 10 11 1 11 12 0 12 13 0 13 14 1 14 15 0 15 16 1 16 17 0 17 18 0 18 19 1 19 20 0 20 21 0 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 1 28 29 0 29 30 0 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 1 ...
output:
41086586 22479083 65941117 52313422 27188549 98552837 41170647 18070874 39704907 37300025 33494097 12541197 85953980 97466762 54255520 55975530 82137682 80760412 36734523 80227468 57771407 53423371 35392992 38772417 24348238 129485865 50694526 41529532 35522018 64188507 64483980 20809109 88158268 62...
result:
ok 50000 numbers
Test #5:
score: 0
Accepted
time: 333ms
memory: 111840kb
input:
50000 100000 1 2 0 2 3 0 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 0 9 10 1 10 11 1 11 12 1 12 13 0 13 14 1 14 15 0 15 16 1 16 17 0 17 18 0 18 19 0 19 20 0 20 21 0 21 22 0 22 23 0 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 0 29 30 1 30 31 1 31 32 0 32 33 0 33 34 1 34 35 0 35 36 0 36 37 0 37 38 0 38 39 0 ...
output:
21363040 19817072 33235630 2642743 12734703 31561956 16868881 12347713 34007395 31539206 21812869 11469295 13583164 35332256 19432281 13050400 27543307 30865175 23535331 10932941 10731700 8935711 32438529 30147704 11201224 15475486 18918233 29097672 1865520 1717197 10847438 17918300 9085519 22377502...
result:
ok 50000 numbers
Test #6:
score: 0
Accepted
time: 393ms
memory: 149560kb
input:
50000 100000 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 0 7 8 1 8 9 0 9 10 1 10 11 0 11 12 1 12 13 0 13 14 1 14 15 0 15 16 1 16 17 1 17 18 0 18 19 1 19 20 1 20 21 1 21 22 0 22 23 1 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 1 30 31 1 31 32 0 32 33 0 33 34 0 34 35 1 35 36 1 36 37 1 37 38 0 38 39 1 ...
output:
7034164 2604311 9210306 13276159 7323558 11457505 5477798 10888155 4546292 13775110 4723690 3315532 7247352 14850537 8847725 7929292 5197554 2059467 7544756 2500593 3970752 12419699 9568962 4563223 10626816 3277034 12260607 6928168 4303017 5299690 8738156 9317082 9746787 10042419 13632702 8481147 11...
result:
ok 50000 numbers
Test #7:
score: 0
Accepted
time: 614ms
memory: 209904kb
input:
50000 100000 1 2 1 2 3 1 3 4 1 4 5 0 5 6 0 6 7 0 7 8 1 8 9 0 9 10 0 10 11 1 11 12 1 12 13 0 13 14 1 14 15 0 15 16 1 16 17 1 17 18 0 18 19 1 19 20 0 20 21 0 21 22 0 22 23 1 23 24 1 24 25 0 25 26 1 26 27 1 27 28 0 28 29 1 29 30 1 30 31 1 31 32 0 32 33 1 33 34 1 34 35 0 35 36 1 36 37 1 37 38 1 38 39 1 ...
output:
2881748 379663 1968885 883510 1429377 1317566 1691388 425238 1498644 703328 976532 252540 2157673 2046415 2184358 1823525 1052010 1808512 1132815 987060 2350191 1248681 2155738 502600 2363042 1527856 2063953 1042845 914460 1787808 1741740 1992040 730062 1592241 1369515 1084786 1140249 2712241 754218...
result:
ok 50000 numbers
Test #8:
score: 0
Accepted
time: 764ms
memory: 243412kb
input:
50000 100000 1 2 1 2 3 1 3 4 0 4 5 1 5 6 1 6 7 0 7 8 0 8 9 1 9 10 1 10 11 0 11 12 0 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 0 18 19 1 19 20 1 20 21 1 21 22 0 22 23 0 23 24 1 24 25 0 25 26 1 26 27 1 27 28 1 28 29 0 29 30 0 30 31 0 31 32 1 32 33 1 33 34 0 34 35 1 35 36 0 36 37 0 37 38 1 38 39 1 ...
output:
196425 220970 672134 128953 248040 374496 332056 388195 69312 404828 506828 470044 440937 427759 304069 412812 560795 698232 549476 191135 57468 173200 255364 763568 250616 668286 251232 71252 152194 430194 671010 10672 671999 197794 308836 393499 324938 191963 182472 234993 495528 453559 86128 9629...
result:
ok 50000 numbers
Test #9:
score: 0
Accepted
time: 773ms
memory: 243948kb
input:
50000 100000 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 0 7 8 0 8 9 0 9 10 0 10 11 1 11 12 0 12 13 1 13 14 0 14 15 0 15 16 1 16 17 1 17 18 0 18 19 1 19 20 1 20 21 0 21 22 1 22 23 1 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 0 36 37 0 37 38 0 38 39 1 ...
output:
468255 105020 312484 469028 46500 433476 348092 241180 416482 136152 497776 571977 530352 219162 562176 138675 705269 353652 287899 214580 13380 294272 27828 132826 749244 506820 295440 417272 370316 114926 552490 6486 834970 359255 601821 208311 337232 101539 489665 169404 93039 64173 382258 775608...
result:
ok 50000 numbers
Test #10:
score: 0
Accepted
time: 778ms
memory: 244592kb
input:
50000 100000 1 2 0 2 3 0 3 4 0 4 5 0 5 6 1 6 7 1 7 8 0 8 9 1 9 10 1 10 11 1 11 12 0 12 13 1 13 14 0 14 15 0 15 16 1 16 17 1 17 18 1 18 19 0 19 20 0 20 21 0 21 22 1 22 23 0 23 24 1 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 0 32 33 0 33 34 1 34 35 1 35 36 0 36 37 0 37 38 0 38 39 1 ...
output:
663010 158597 758130 682380 443574 514836 623881 348012 155945 542531 400539 240444 166313 307926 556860 383720 97095 367865 372270 204195 787005 79165 455970 495416 156456 33165 223166 481715 416854 524138 316025 105263 274806 781025 177352 653420 491795 743770 506808 72480 505734 444805 198372 700...
result:
ok 50000 numbers
Test #11:
score: 0
Accepted
time: 60ms
memory: 12268kb
input:
50000 99998 1 2 0 1 2 1 2 3 0 2 3 1 3 4 0 3 4 1 4 5 0 4 5 1 5 6 0 5 6 1 6 7 0 6 7 1 7 8 0 7 8 1 8 9 0 8 9 1 9 10 0 9 10 1 10 11 0 10 11 1 11 12 0 11 12 1 12 13 0 12 13 1 13 14 0 13 14 1 14 15 0 14 15 1 15 16 0 15 16 1 16 17 0 16 17 1 17 18 0 17 18 1 18 19 0 18 19 1 19 20 0 19 20 1 20 21 0 20 21 1 21...
output:
357392852 286944261 25899482 106697866 266744665 188046239 246595068 282194356 149697006 36449271 55148897 105197896 112647747 361542769 153346933 426991460 799984 17749645 256444871 329993400 275444491 344593108 81998360 305443891 233695326 82148357 92148157 17449651 36449271 34349313 175796484 354...
result:
ok 50000 numbers
Test #12:
score: 0
Accepted
time: 196ms
memory: 174772kb
input:
50000 50299 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 8 0 8 9 0 9 10 0 10 11 0 11 12 0 12 13 0 13 14 0 14 15 0 15 16 0 16 17 0 17 18 0 18 19 0 19 20 0 20 21 0 21 22 0 22 23 0 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 0 32 33 0 33 34 0 34 35 0 35 36 0 36 37 0 37 38 0 38 39 0 3...
output:
28885380 45069427 33432760 30206043 5611707 40119773 20814082 10397200 11616787 7910426 49163370 9368174 31732491 43615079 41538187 27076798 41917819 32019460 17871476 14080806 5899035 42800174 14990686 29049896 25022003 9316314 27915136 19878279 43675167 30658188 2990993 2704160 12805154 19507614 5...
result:
ok 50000 numbers