QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799902#9352. Highway BusesBINYUML 151ms180224kbC++145.6kb2024-12-05 19:28:162024-12-05 19:28:20

Judging History

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

  • [2024-12-10 15:19:00]
  • hack成功,自动添加数据
  • (/hack/1277)
  • [2024-12-05 19:28:20]
  • 评测
  • 测评结果:ML
  • 用时:151ms
  • 内存:180224kb
  • [2024-12-05 19:28:16]
  • 提交

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

output:


result: