QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799902 | #9352. Highway Buses | BINYU | ML | 151ms | 180224kb | C++14 | 5.6kb | 2024-12-05 19:28:16 | 2024-12-05 19:28:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct IO {
static const int inSZ = 1 << 17;
char inBuf[inSZ], *in1, *in2;
template<class T> inline __attribute((always_inline))
T read() {
if (in1 > inBuf + inSZ - 32) [[unlikely]] {
auto len = in2 - in1;
memcpy(inBuf, in1, len);
in1 = inBuf, in2 = inBuf + len;
in2 += fread(in2, 1, inSZ - len, stdin);
if (in2 != inBuf + inSZ) *in2 = 0;
}
T res = 0;
unsigned char c;
bool neg = 0;
while ((c = *in1++) < 48) neg = c == 45;
while (res = res * 10 + (c - 48), (c = *in1++) >= 48);
return neg ? -res : res;
}
static const int outSZ = 1 << 21;
char outBuf[outSZ], *out;
template<class T> inline __attribute((always_inline))
void write(T x) {
if (out > outBuf + outSZ - 32) [[unlikely]]
{
fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
}
if (!x) return *out++ = 48, void();
if (x < 0) *out++ = 45, x = -x;
alignas(2) const char* digits =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";
alignas(64) static char buf[20];
char* p = buf + 20;
while (x >= 10) memcpy(p -= 2, digits + x % 100 * 2, 2), x /= 100;
if (x) *--p = 48 + x;
auto len = buf + 20 - p;
memcpy(out, p, len), out += len;
}
void init() {
in1 = in2 = inBuf + inSZ;
out = outBuf;
}
~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;
template<class T = int> inline T read() {
return IO.read<T>();
}
template<class T> inline void print(T x, char c) {
IO.write(x), *IO.out++ = c;
}
template<class T> inline void print(T x) {
IO.write(x);
}
inline __attribute((always_inline)) void printCh(char c) {
*IO.out++ = c;
}
#define pii pair <int,int>
#define pli pair <ll,int>
#define fi first
#define se second
#define ll long long
const int N = 2e5,M = 50;
int n,m,u,v,cnt,a[N + 5],b[N + 5],f[N + 5],vis[N + 5],siz[N + 5];
int Dis[N + 5],dis[M + 5][N + 5],t1[M + 5],t2[N + 5];
int T,c[N + 5],w[N + 5];
ll d[N + 5],ans[N + 5],C[N + 5];
priority_queue <pli,vector <pli>,greater <pli> > q;
queue <int> Q;
struct edge
{
int v,nxt;
}e[2 * N + 5];
int head[N + 5],cnte;
struct Edge
{
int v,nxt;
}E[2 * N + 5];
int Head[N + 5],cntE;
void adde(int u,int v)
{
e[++cnte] = {v,head[u]};head[u] = cnte;
}
void addE(int u,int v)
{
E[++cntE] = {v,Head[u]};Head[u] = cntE;
}
vector <pii> c2[N + 5];
pii c1[M + 5][N + 5];
unordered_map <int,int> mp[N + 5];
struct DSU
{
int f[N + 5];
void init(int n)
{
for(int i = 1;i <= n;i++)f[i] = i;
}
int fnd(int x)
{
return x == f[x] ? x : f[x] = fnd(f[x]);
}
bool merge(int x,int y)
{
x = fnd(x);y = fnd(y);
if(x == y)return 0;
f[x] = y;
return 1;
}
}dsu;
int get_siz(int u,int fa)
{
siz[u] = 1;
for(int i = head[u];i;i = e[i].nxt)
if(!vis[e[i].v]&&e[i].v != fa)
siz[u] += get_siz(e[i].v,u);
return siz[u];
}
int get_root(int u,int fa,int Siz)
{
int mx = Siz - siz[u],rt = -1;
for(int i = head[u];i;i = e[i].nxt)
if(!vis[e[i].v]&&e[i].v != fa)
mx = max(mx,siz[e[i].v]),
rt = max(rt,get_root(e[i].v,u,Siz));
if(mx * 2 <= Siz)return u;
return rt;
}
void init1(int st,int *dis,pii *c)
{
Q.push(st);dis[st] = 0;int cnt = 0;
while(!Q.empty())
{
int u = Q.front();Q.pop();
c[cnt++] = {dis[u],u};
for(int i = Head[u];i;i = E[i].nxt)
if(E[i].v != st&&!dis[E[i].v]&&!vis[E[i].v])
dis[E[i].v] = dis[u] + 1,Q.push(E[i].v);
}
}
void init2(int st,int *dis,vector <pii> &c)
{
Q.push(st);dis[st] = 0;
while(!Q.empty())
{
int u = Q.front();Q.pop();
c.push_back({dis[u],u});
mp[st][u] = dis[u];
for(int i = head[u];i;i = e[i].nxt)
if(e[i].v != st&&!dis[e[i].v]&&!vis[e[i].v])
dis[e[i].v] = dis[u] + 1,Q.push(e[i].v);
}
for(auto now : c)dis[now.second] = 0;
}
int solve(int u)
{
vis[u] = 1;init2(u,Dis,c2[u]);
for(int i = head[u];i;i = e[i].nxt)
if(!vis[e[i].v])
f[solve(get_root(e[i].v,u,get_siz(e[i].v,u)))] = u;
return u;
}
void dij(ll x)
{
for(int i = 1;i <= n;i++)
C[i] = c[i] + w[i] * x,d[i] = vis[i] = t1[i] = t2[i] = 0;
q.push({0,1});vis[1] = 1;
while(!q.empty())
{
int u = q.top().second;q.pop();
for(int i = 1;i <= cnt;i++)
{
int noww = b[u] - dis[i][u];
while(t1[i] < n)
{
int v = c1[i][t1[i]].second;
if(c1[i][t1[i]].first > noww)break;
if(!vis[v])
d[v] = d[u] + C[u],vis[v] = 1,
q.push({d[v] + C[v],v});
t1[i]++;
}
}
int now = u;
while(now)
{
int noww = b[u] - mp[now][u];
while(t2[now] != c2[now].size())
{
int v = c2[now][t2[now]].second;
if(c2[now][t2[now]].first > noww)break;
if(!vis[v])
d[v] = d[u] + C[u],vis[v] = 1,
q.push({d[v] + C[v],v});
t2[now]++;
}
now = f[now];
}
}
for(int i = 1;i <= n;i++)ans[i] = min(ans[i],d[i]);
}
int main()
{
IO.init();
n = read();m = read();T = read();
dsu.init(n);
for(int i = 1;i <= n;i++)
b[i] = read(),c[i] = read(),w[i] = read();
for(int i = 1;i <= m;i++)
{
u = read(),v = read();
addE(u,v);addE(v,u);
if(dsu.merge(u,v))adde(u,v),adde(v,u);
else a[++cnt] = u;
}
for(int i = 1;i <= cnt;i++)init1(a[i],dis[i],c1[i]);
solve(get_root(1,0,get_siz(1,0)));
memset(ans,0x3f,sizeof(ans));
dij(0);dij(T - 1);
for(int i = 1;i <= n;i++)print(ans[i],'\n');
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 37300kb
input:
6 6 2 1 50 -40 1 2 100 2 1 100 2 4 100 3 1 100 1 1 100 1 2 2 3 3 4 4 2 2 5 6 1
output:
0 10 52 52 52 10
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 138152kb
input:
500 540 1000000 1 831790353 70 3 624594642 -127 2 189318946 -92 1 858646508 320 4 76999645 671 4 780012318 880 2 51254764 -12 2 420182468 -333 3 314764053 -36 1 560114854 -419 2 484412868 -31 3 466851594 6 4 535326027 732 4 430602789 578 1 605236859 43 4 633715178 896 3 110060408 -9 4 878946915 -654...
output:
0 1277292628 1239671692 1255261807 1284074004 1270230633 1239671692 1284074004 1271369537 1277292628 1205507860 1270615693 1300179417 1205507860 1205507860 1239671692 1251564675 1239671692 1284004371 1239671692 1239671692 1277292628 1270230633 1284004371 1277292628 1255261807 1276194392 1247939403 1...
result:
ok 500 lines
Test #3:
score: 0
Accepted
time: 8ms
memory: 134980kb
input:
500 540 1000000 1 613142394 -268 5 920609625 740 2 755612530 -255 2 23678897 -4 5 325892468 291 5 707223319 -140 1 679600699 -138 5 625157055 690 2 141819870 995 1 250348582 -219 2 581461324 -580 4 339782234 -82 5 810851082 230 3 378119535 158 4 295102386 677 5 854435300 21 3 565535907 -465 2 820995...
output:
0 2421015760 2617367920 2694215005 2812156460 2412108889 2370843291 2786283443 2412108889 2197157944 2412108889 2633707306 2370843291 2478757415 2672183755 2478757415 2633707306 2812156460 1984181483 2464420418 2548091380 2421015760 2421015760 2412108889 2421015760 2421015760 2412108889 2412108889 2...
result:
ok 500 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 141692kb
input:
500 544 1000000 2 587500219 -573 3 800375803 -606 2 332196789 -11 2 782258272 270 2 690828422 -145 2 642751384 -107 4 78645508 -68 3 692764955 364 5 739361677 -104 4 139030619 -125 5 698401632 -121 3 654935300 401 4 70734757 -57 2 763502749 911 1 71485824 836 1 292976518 -290 1 743618801 659 2 64895...
output:
0 425794735 442014967 675968705 311908134 675968705 336563578 425794735 523701048 479984544 425794735 425794735 425794735 708001283 311908134 1653971237 425794735 580659172 425794735 487630114 311908134 450399440 1653971237 425957613 425794735 425957613 336604992 336604992 425794735 436034689 425794...
result:
ok 500 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 137896kb
input:
500 543 1000000 4 753661240 -312 2 281450837 -151 9 28464686 987 7 685967710 490 8 592650944 542 10 141100249 83 10 646501804 -94 3 337312645 294 2 904175548 -870 8 281667853 -136 3 36477141 -26 5 476645115 -195 1 21897824 -7 10 517151723 150 1 291410319 941 7 993616997 143 10 628559241 -428 8 10757...
output:
0 445387723 445387723 450719457 455897864 445387723 449974501 449974501 449974501 444157947 449974501 449974501 449974501 449974501 449974501 445387723 441661552 449974501 449974501 449974501 444157947 444157947 444157947 449974501 444157947 444157947 449974501 445387723 441661552 449974501 45156161...
result:
ok 500 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 154444kb
input:
500 547 1000000 7 579418 0 1 769742 0 1 133755 0 2 996071 0 2 96075 893 7 484503 0 7 645976 141 6 80570 0 2 33751 124 4 218617 701 5 686104 0 1 675119 586 3 294461 0 5 319865 0 9 178301 179 1 547068 0 1 96921 802 3 725739 58 8 646648 0 4 667865 0 6 816462 0 4 901406 37 4 834211 0 1 364051 263 2 1014...
output:
0 653962 626600 579418 626600 603269 603269 626600 626600 634782 626600 672297 579418 626600 626600 579418 626600 579418 626600 672297 626600 661975 672297 746441 626600 661975 626600 626600 626600 626600 579418 626600 653962 661975 626600 626600 579418 579418 626600 579418 579418 626600 634782 6266...
result:
ok 500 lines
Test #7:
score: 0
Accepted
time: 8ms
memory: 159544kb
input:
500 549 1000000 8 275979 799 2 323404 0 8 286448 610 2 877230 292 5 111405 972 2 686865 757 6 542128 0 9 823472 705 8 551203 0 9 900802 0 8 497319 554 2 60284 473 1 128784 147 1 390099 282 1 376548 407 7 444338 502 10 496911 293 7 133528 0 1 949531 669 8 569605 459 1 310534 504 2 705803 0 5 954861 0...
output:
0 308634 296602 275979 275979 275979 308634 296754 296602 275979 296602 308634 275979 275979 275979 296602 275979 296602 275979 296602 308634 296602 275979 300889 275979 275979 275979 275979 296754 296602 324141 275979 296754 296754 308634 296602 308634 308634 275979 296754 275979 275979 324141 2759...
result:
ok 500 lines
Test #8:
score: 0
Accepted
time: 142ms
memory: 174092kb
input:
30000 30047 786577 2 418118 886 1 923620 -1 1 396304 59 1 357673 0 1 12272 51 2 797480 0 2 41479 797 1 970539 -1 1 608143 0 2 415150 0 1 459616 0 1 739232 742 1 917012 -1 1 165211 0 1 637917 550 1 238131 0 2 232835 258 2 610877 0 1 17235 0 2 112947 446 2 828314 0 2 179873 782 2 333590 0 1 961918 194...
output:
0 80494179 83741087 62038907 76473105 104910654 116145079 108446496 88716481 94285072 115284209 99860695 77584533 119165550 81758989 77570762 142596283 79902868 77267149 95599129 114945135 73806480 108069554 77051483 76742645 57016312 152581721 89223155 76282889 122548472 23429774 107080496 76205230...
result:
ok 30000 lines
Test #9:
score: 0
Accepted
time: 151ms
memory: 180224kb
input:
30000 30050 605850 9 564340 974 2 843284 -1 1 398311 922 9 478997 556 7 671058 -1 3 671222 872 2 943222 -1 3 357119 393 8 108556 258 2 579805 0 5 452884 0 7 578644 871 4 863186 157 8 47757 0 10 635134 678 4 73374 1000 4 614076 0 3 549192 0 8 945587 0 5 67239 48 5 943401 992 9 345170 459 6 164234 0 5...
output:
0 9452611 15305660 6254895 8166386 10065348 6017741 6884440 17917177 6017741 7241812 5274395 6017741 6017741 10160098 6017741 8872246 7061933 10080339 8597089 5885039 6017741 6017741 12747501 7589567 13233135 6017741 12499965 6017741 8353713 11425708 6017741 6017741 6017741 7468089 8335888 9588729 6...
result:
ok 30000 lines
Test #10:
score: -100
Memory Limit Exceeded
input:
200000 200047 812175 1 850300 0 1 913813 609 1 148997 755 1 5275 0 1 989899 -1 1 843074 -1 1 131757 0 1 713341 0 1 530046 919 1 243794 0 1 127575 558 1 385431 694 1 94653 0 1 556880 189 1 718137 564 1 968120 -1 1 358633 973 1 2321 0 1 331378 0 1 164889 583 1 70541 710 1 338259 54 1 866090 73 1 31800...