QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462605#553. 王国LXl491214100 ✓30ms19076kbC++142.9kb2024-07-03 22:00:462024-07-03 22:00:46

Judging History

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

  • [2024-07-03 22:00:46]
  • 评测
  • 测评结果:100
  • 用时:30ms
  • 内存:19076kb
  • [2024-07-03 22:00:46]
  • 提交

answer

#include <iostream>
#include <cstring>
using namespace std;
constexpr const int mod = 1000000007;
constexpr int OFR(const int val)
{
	return val >= mod ? val - mod : val;
}
constexpr int UFR(const int val)
{
	return val < 0 ? val + mod : val;
}
constexpr void UpdMin(int &a, const int b)
{
	if (a > b)
		a = b;
	return;
}
char buf[16777216], *p_in = buf;
int ReadU()
{
	while (*p_in < '0')
		++p_in;
	int ans = *p_in ^ '0';
	while (*(++p_in) >= '0')
		ans = ans * 10 + (*p_in ^ '0');
	return ans;
}
int siz_edge, sum_m, ans1, edges[100001], m[100001], sum_dis[100001], l[1000001], c[1000001], sum_c[1000001], f[500005], tag[1000001];
long long sum_l[1000001];
struct Edge
{
	int dest, next, t;
} edge[200002];
void Link(const int source, const int dest, const int t)
{
	edge[++siz_edge].next = edges[source];
	edge[edges[source] = siz_edge].dest = dest;
	edge[siz_edge].t = t;
	return;
}
void DFS(const int pos, const int parent)
{
	ans1 = (ans1 + 1ull * (sum_m - m[pos]) * sum_dis[pos]) % mod;
	for (int i = edges[pos]; i; i = edge[i].next)
		if (edge[i].dest != parent)
		{
			DFS(edge[i].dest, pos);
			ans1 = (ans1 + 1ull * m[edge[i].dest] * (sum_m - m[edge[i].dest]) % mod * edge[i].t) % mod;
			m[pos] += m[edge[i].dest];
		}
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin.read(buf, sizeof(buf));
	const int n = ReadU();
	for (int i = 1; i < n; ++i)
	{
		const int u = ReadU(), v = ReadU(), t = ReadU();
		Link(u, v, t);
		Link(v, u, t);
	}
	int ans2 = 0;
	for (int i = 1; i <= n; ++i)
	{
		const int m = ::m[i] = ReadU() - 1, m2 = m * 2;
		sum_m += m;
		for (int j = 1; j <= m; ++j)
			l[j + m] = l[j] = ReadU();
		for (int j = 1; j <= m; ++j)
			c[j + m] = c[j] = ReadU();
		for (int j = 1; j < m2; ++j)
			UpdMin(c[j + 1], c[j] + l[j]);
		for (int j = m2 - 1; j; --j)
			UpdMin(c[j], c[j + 1] + l[j]);
		unsigned long long sd = 0;
		for (int j = 1; j <= m; ++j)
		{
			UpdMin(c[j], c[j + m]);
			sd += c[j + m] = c[j];
		}
		sum_dis[i] = sd % mod;
		for (int j = 1; j < m2; ++j)
		{
			sum_c[j] = OFR(sum_c[j - 1] + c[j]);
			sum_l[j + 1] = sum_l[j] + l[j];
		}
		sum_c[m2] = OFR(sum_c[m2 - 1] + c[m2]);
		int p = 1;
		for (int j = 1; j <= m; ++j)
		{
			const int jPm = j + m;
			while (sum_l[p] - sum_l[j] < c[j] + c[p] && sum_l[p] - sum_l[j] <= sum_l[jPm] - sum_l[p])
				++p;
			tag[j] += (f[j] = p - 1) - j;
			tag[j + 1] -= p - j;
			++tag[p];
		}
		for (int j = 1, a = 0, b = 0; j <= p; ++j)
		{
			b += a += tag[j];
			tag[j] = 0;
			ans1 = (ans1 + 1ull * b * l[j]) % mod;
		}
		p = m2 - 1;
		for (int j = m; j; --j)
		{
			const int jPm = j + m;
			while (sum_l[jPm] - sum_l[p] < c[jPm] + c[p] && sum_l[jPm] - sum_l[p] < sum_l[p] - sum_l[j])
				--p;
			ans2 = (ans2 + 1ull * (p - f[j]) * c[j] + (sum_c[p] + mod - sum_c[f[j]])) % mod;
		}
	}
	DFS(1, 0);
	cout << OFR(OFR(ans1 * 2) + ans2);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 3580kb

input:

10
1 2 50
2 3 59
2 4 73
1 5 79
4 6 10
1 7 66
1 8 43
4 9 4
8 10 30
8
39 2 72 38 78 95 10
45 98 29 59 98 5 32
10
46 36 43 69 61 95 96 14 7
76 99 100 13 58 9 69 31 63
9
43 83 68 96 72 91 39 17
66 53 22 13 2 32 58 91
14
41 36 73 96 55 90 6 24 14 39 21 67 27
80 7 99 20 24 61 27 7 71 95 45 35 95
10
64 45 ...

output:

1956394

result:

ok single line: '1956394'

Test #2:

score: 10
Accepted
time: 1ms
memory: 3608kb

input:

5
1 2 250
2 3 659
2 4 273
1 5 879
20
439 502 872 138 178 295 610 746 636 143 969 261 595 396 114 7 943 83 768
145 898 829 359 398 905 232 176 299 400 413 558 9 969 531 963 366 853 822
18
696 672 591 739 617 641 336 973 96 455 290 906 124 814 239 221 367
713 902 832 58 791 680 7 99 320 224 761 127 50...

output:

15675138

result:

ok single line: '15675138'

Test #3:

score: 10
Accepted
time: 3ms
memory: 4556kb

input:

10000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
...

output:

453173522

result:

ok single line: '453173522'

Test #4:

score: 10
Accepted
time: 22ms
memory: 13320kb

input:

100000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822...

output:

181864911

result:

ok single line: '181864911'

Test #5:

score: 10
Accepted
time: 5ms
memory: 10188kb

input:

1
100001
990117072 121266257 502101444 506187797 152265724 887855716 21575364 747489891 3913373 252828825 925488373 869945258 957255916 909604725 337241170 254650067 235485017 619901983 240912374 769328282 249600354 66310996 621433473 134246045 799368852 533841194 911465239 114696140 236494004 44433...

output:

672785783

result:

ok single line: '672785783'

Test #6:

score: 10
Accepted
time: 24ms
memory: 15564kb

input:

10
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
49733
22624218 300982665 75514183 17307023 151891674 818814124 681421086 983939896 975213637 388337097 728609775 503839345 909679593 275227646 722966525 313571842 143077312 3...

output:

5175380

result:

ok single line: '5175380'

Test #7:

score: 10
Accepted
time: 28ms
memory: 13500kb

input:

100
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
14...

output:

691155161

result:

ok single line: '691155161'

Test #8:

score: 10
Accepted
time: 22ms
memory: 13248kb

input:

1000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
1...

output:

265274205

result:

ok single line: '265274205'

Test #9:

score: 10
Accepted
time: 22ms
memory: 13892kb

input:

10000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822
...

output:

682655928

result:

ok single line: '682655928'

Test #10:

score: 10
Accepted
time: 30ms
memory: 19076kb

input:

100000
1 2 282475250
2 3 984943659
2 4 470211273
1 5 457850879
4 6 7237710
1 7 115438166
1 8 74243043
4 9 137522504
8 10 16531730
1 11 143542613
7 12 474833170
10 13 998097158
13 14 131570934
14 15 404280279
12 16 505795336
10 17 636807827
1 18 101929268
9 19 704877634
2 20 624379150
20 21 784558822...

output:

702441060

result:

ok single line: '702441060'