QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #120664 | #6660. 택시 여행 | platelet# | 0 | 70ms | 114688kb | C++17 | 2.1kb | 2023-07-07 09:18:17 | 2024-05-26 01:46:48 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
template<class T> inline T& cmin(T& a, const T& b) { if(b < a) a = b; return a; }
template<class T> inline T& cmax(T& a, const T& b) { if(a < b) a = b; return a; }
template<class... Args> void print(Args&&... args) {
#ifdef local
((cout << args << ' '), ...);
#endif
}
template<class... Args> void println(Args&&... args) {
#ifdef local
print(args...), cout << endl;
#endif
}
const int N = 1e5 + 8;
ll a[N], ans[N];
int b[N];
vector<pair<int, int>> G[N];
struct Line {
ll k, b;
ll operator () (ll x)const {
return k * x + b;
}
};
int idx;
struct {
int l, r;
Line x;
} c[N * 40];
int insert(Line x, ll l, ll r, int o) {
ll L1 = x(l), R1 = x(r), L2 = c[o].x(l), R2 = c[o].x(r);
if(L1 >= L2 & R1 >= R2) return o;
int oo = ++idx;
c[oo] = c[o];
if(L1 <= L2 & R1 <= R2) return c[oo].x = x, oo;
ll m = (l + r) >> 1;
c[oo].l = insert(x, l, m, c[oo].l);
c[oo].r = insert(x, m + 1, r, c[oo].r);
return oo;
}
ll query(ll i, ll l, ll r, int o) {
ll res = 1e18;
while(o) {
cmin(res, c[o].x(i));
ll m = (l + r) >> 1;
tie(l, r, o) = i <= m ? tuple(l, m, c[o].l) : tuple(m + 1, r, c[o].r);
}
return res;
}
void dfs(int u, int f, int o, ll dep) {
if(u) ans[u] = query(dep, 0, 1e11, o);
o = insert({b[u], ans[u] + a[u] - dep * b[u]}, 0, 1e11, o);
for(auto [v, w] : G[u]) if(v != f)
dfs(v, u, o, dep + w);
}
vector<ll> travel(vector<ll> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W) {
For(i, 0, SZ(A)) a[i] = A[i], b[i] = B[i];
For(i, 0, SZ(U)) G[U[i]].eb(V[i], W[i]), G[V[i]].eb(U[i], W[i]);
c[0].x = {0, (ll)1e18};
dfs(0, 0, 0, 0);
return vector(ans + 1, ans + SZ(A));
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 1ms
memory: 8488kb
input:
2 684124582850 713748627948 74361 256955 0 1 661088
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 733283747618 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 9016kb
input:
3 251115773325 363097865287 358609487841 826785 213106 914768 0 1 851938 2 0 231697
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 955485332655 442679377470 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 8592kb
input:
3 489998888627 318672977903 70353752652 258347 458793 258657 2 1 156120 0 2 524840
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 665922861747 625589728107 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 8496kb
input:
3 737471938521 315388610250 818943569900 726908 666797 564862 0 1 460302 0 2 785280
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1072069144737 1308298252761 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 4 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 9052kb
input:
4 201836820267 208957719162 992553400562 566050337171 243994 65303 590123 936951 1 0 259719 0 3 860376 3 2 513584
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 265206697953 537074816507 411763402011 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 9008kb
input:
4 440719935569 160237864481 704297665373 767778991240 451998 371509 46564 828427 1 0 861960 1 3 830699 2 3 185693
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 830324131649 1289731282865 1205798418251 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 1ms
memory: 9876kb
input:
5 148262899914 9382086008 622202345986 443806901161 213829280326 178155 503016 333953 572340 461148 0 3 453941 3 2 84057 4 0 171136 3 1 598794
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 335812903839 244109933604 229134758769 178751633994 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 6 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 8244kb
input:
5 391440982512 969252165920 333946610796 649830522527 902812044171 522045 996458 225429 545971 667483 0 1 701500 0 4 514779 2 1 435377 3 0 919439
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 757655550012 984941935977 871429515267 660178785567 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
ok 6 lines
Test #9:
score: -7
Wrong Answer
time: 2ms
memory: 9928kb
input:
17 315015458526 65513576283 829720084774 654640079244 561177336848 463903843105 496216524512 837433489064 92734412345 807145138979 250511786518 915329126804 373916658654 78276842047 121976569238 432447179015 519384539551 696133 642473 231377 987220 589587 337763 790202 785083 249580 108311 73808 892...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 430639669161 417840567823 403532946274 854701616505 811025535952 634227941809 877731088411 1019176960415 796723483467 1008215650197 474661031682 536446316097 411867746683 749241643803 907444829383 704895883304 secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I
result:
wrong answer 5th lines differ - expected: '499079112962', found: '854701616505'
Subtask #2:
score: 0
Runtime Error
Test #31:
score: 8
Accepted
time: 62ms
memory: 66156kb
input:
100000 746699125678 374834842799 250803643493 620187038832 454433387570 406226564003 897157438699 99473514061 734784419618 503968957100 363935477037 277126009840 52078020050 990757079812 847235285349 950784717285 271017141367 861087225700 996035427219 520682200664 282013988419 415183977876 882007771...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1148030742334 1636760433058 2131282232650 2353514637869 2672707119337 2763307672337 2948215735597 3003888852169 3054019822989 3117708941277 3168979051095 3214001638323 3269286229765 3273106480907 3287227043365 3335909595067 3361857042147 3364657567217 338173015...
result:
ok 100001 lines
Test #32:
score: 0
Accepted
time: 70ms
memory: 65412kb
input:
99999 199936403206 387848228799 134551775973 379377394692 83082074622 879859342494 648173966597 944650644236 499996263229 902471096917 590863268927 40584929392 906714919013 233728229536 286705399400 944576541664 998941389868 610718110168 422760120374 346110411150 812871715907 273865436932 3195132627...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 697799158816 929607027922 1018095086086 1584613641145 1877765365665 2239699168305 2438089294735 2832345576485 2927526977455 2931605531105 3195571528127 3387289232535 3446336905209 3460262616504 3466765570662 3469379135670 3491001700992 3497511229992 35078529774...
result:
ok 100000 lines
Test #33:
score: 0
Accepted
time: 47ms
memory: 68872kb
input:
100000 56998 11671 13811 25717 14858 88240 42443 83814 1000000000000 76043 96812 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 96423 8620 1000000000000 1000000000000 21485 33558 27910 1000000000000 1000000000000 1000000000000 1000000000000 88572 61826 1000000000000 22580 8911...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 350836056998 1268196151308 1761927177655 1764058173393 1823989948523 2593985186768 3180555709767 3397318276233 3865405999596 4662149904880 5500125621852 5885446768602 6399152631492 6942124201722 7571623906662 7578166841232 7924285399671 8079299773002 8229842213...
result:
ok 100001 lines
Test #34:
score: 0
Accepted
time: 37ms
memory: 84948kb
input:
100000 14710 1000000000000 25745 978 1000000000000 62317 22444 1000000000000 8347 1000000000000 33719 65677 98665 62278 1000000000000 1000000000000 37800 67542 58652 1000000000000 1000000000000 25465 12743 31814 1000000000000 92966 22056 1000000000000 1067 24490 9396 1000000000000 17174 19345 31055 ...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 881904014710 1542423014710 2233996657305 3033138260851 3818801903853 3910348508435 4546837711921 5257126450163 6187656014214 6382291457118 6984889464797 7158062625549 7640143939170 8471766190219 9461415324613 9768735329401 10038031058401 10588178773274 10854900...
result:
ok 100001 lines
Test #35:
score: 0
Accepted
time: 66ms
memory: 87648kb
input:
94827 22402 62109 33267 89192 1000000000000 34994 26802 11762 1000000000000 58525 1000000000000 1000000000000 1000000000000 86073 31536 30063 1370 54650 53651 9657 1000000000000 1000000000000 1000000000000 23604 38641 56775 26468 43548 33809 74580 1000000000000 1000000000000 92571 1000000000000 1922...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 506781022402 551887022402 1470591218257 1570575007497 2060293538337 2717768285941 3403176200271 3411252151815 3928574534219 4656961037207 5072868294008 6057420432959 6341875872837 7155710378925 7542794991201 7788796331189 8003459897887 8625555376735 93472504396...
result:
ok 94828 lines
Test #36:
score: 0
Accepted
time: 68ms
memory: 97500kb
input:
100000 13783 1000000000000 1000000000000 28609 82477 1000000000000 66631 31765 79413 54284 21977 98114 1000000000000 1000000000000 12294 21853 99221 67993 13506 87091 96991 1000000000000 1000000000000 1000000000000 78773 52607 1000000000000 12382 51767 1000000000000 1000000000000 1000000000000 58422...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 853169013783 1385838013783 1798533013783 1999567439287 2984456582192 3412540869848 3596703831495 3830162229040 4210874262733 4322399313283 5000201557170 5773654147213 6267343716568 6939334324590 7300134285614 7563570355867 7825168269456 8299451274502 9199219091...
result:
ok 100001 lines
Test #37:
score: 0
Accepted
time: 64ms
memory: 114688kb
input:
99013 25311 10149 92055 18621 30464 42738 57404 26228 89765 49821 86564 88474 58867 28911 70528 47489 77906 45409 2235 839 71138 53163 32524 47258 7663 27526 89795 51926 53217 10161 1675 23003 31180 35502 48694 60585 66045 69603 90269 35308 6985 1668 92978 16505 3949 52801 27047 1634 23493 24546 942...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 952085025311 1608027379517 2267132153360 2377639840457 2476220476597 2852709636880 2887654462155 3242135007002 3781302783391 4649627018224 5172774873258 5666844526907 5954087138822 6202983932033 6393508335183 7292230901632 7607428936290 8402727461395 9320371945...
result:
ok 99014 lines
Test #38:
score: -8
Runtime Error
input:
100000 41470 86167 38125 18891 51474 6401 24258 23148 98577 49813 31436 14447 76256 34760 17176 16188 52035 91332 30657 51668 70484 42793 98864 97559 75171 84727 82885 37141 61138 36539 63298 95576 91623 15468 94434 99763 32482 67115 88955 32740 2367 72772 41787 92407 85389 64331 7555 69817 2842 351...
output:
Unauthorized output
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 46ms
memory: 24236kb
input:
100000 15175010 23519365 21177669 27079342 9089 16784452 29693960 23124925 17048604 10179491 12828214 24992902 8483134 2928073 23807522 7332137 17421520 28460746 1607282 13224363 11900728 11794692 11495061 4687109 23460275 7657982 27417256 16978162 7326803 23083826 24942987 16610314 12147303 2828271...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 30113234 24595570 19218106 28342690 20284122 22367858 20984498 31475330 31052590 25650594 24557802 29686714 29034010 20541602 31270354 28887570 19996674 23776338 20744026 27884050 24816302 29137106 25889946 33355562 32888514 20197570 26793946 19267922 36558578 ...
result:
wrong answer 2nd lines differ - expected: '16705757', found: '30113234'
Subtask #5:
score: 0
Wrong Answer
Test #94:
score: 0
Wrong Answer
time: 38ms
memory: 21776kb
input:
99281 551670361798 568902251563 418071776626 697635341894 641578820039 117221079324 812766431051 425410617978 663769685693 282144284527 799662290178 749088952784 586626406385 122473825417 459510657357 871705247919 443707710712 735612808044 237919555727 829939639783 122127143240 616906466299 24431898...
output:
secret: XBNN6R0Jnospxlfz11GWxd4ldkzb0I 1562976347774 1132382933310 1003286856182 1147805537237 730621710202 1143631405862 1301052670694 1834925695317 1309483119193 1793817336000 1077624511454 1362987791970 1302691006533 1379976091919 1362987791970 1567199347334 1673956920958 901601060214 13403927884...
result:
wrong answer 2nd lines differ - expected: '598598746654', found: '1562976347774'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%