QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#6986#553. 王国govanitics100 ✓262ms28716kbC++984.4kb2021-03-19 13:27:182021-12-19 10:00:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 10:00:08]
  • 评测
  • 测评结果:100
  • 用时:262ms
  • 内存:28716kb
  • [2021-03-19 13:27:18]
  • 提交

answer

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100005, MOD = 1000000007, M = 500005 << 1;
int n, m[N], msum, tcd[N], size[N], totcd[N];

vector<pair<int, int> > edge[N];

vector<int> l[N], c[N];

int dfs(int u, int fa = -1) {
	int ret = tcd[u];
	size[u] = m[u];
	for (int i = 0; i < (int)edge[u].size(); ++i) {
		int v = edge[u][i].first, w = edge[u][i].second;
		if (v == fa) {
			continue;
		}
		int vd = dfs(v, u);
		size[u] += size[v];
		(ret += (vd + (long long)size[v] * w % MOD) % MOD) %= MOD;
	}
	return ret;
}

void dfs2(int u, int fa = -1) {
	for (int i = 0; i < (int)edge[u].size(); ++i) {
		int v = edge[u][i].first, w = edge[u][i].second;
		if (v == fa) {
			continue;
		}
		totcd[v] = (totcd[u] + (long long)(msum - size[v] * 2) * w) % MOD;
		if (totcd[v] < 0) {
			totcd[v] += MOD;
		}
		dfs2(v, u);
	}
}

int curn, csum[M], cordSum[M];

long long cord[M];

void init(int n, vector<int> &l, vector<int> &c) {
	curn = n;
	cord[0] = 0;
	for (int i = 0; i <= 2 * n; ++i) {
		cord[i + 1] = cord[i] + l[i % n];
	}
	cordSum[0] = 0;
	for (int i = 0; i <= 2 * n; ++i) {
		cordSum[i + 1] = (cordSum[i] + cord[i]) % MOD;
	}
	csum[0] = 0;
	for (int i = 0; i <= 2 * n; ++i) {
		csum[i + 1] = (csum[i] + c[i % n]) % MOD;
	}
}

long long getDis(int l, int r) {
	if (r < l) {
		r += curn;
	}
	return cord[r] - cord[l];
}

int getDisTC(int l, int r) {
	if (r < l) {
		r += curn;
	}
	return (csum[r + 1] - csum[l] + MOD) % MOD;
}

int getDisSum(int l, int r) {
	if (r < l) {
		r += curn;
	}
	int cnt = r - l;
	return ((long long)cord[r] * cnt % MOD - (cordSum[r] - cordSum[l]) % MOD + MOD) % MOD;
}

int getDisSumR(int l, int r) {
	if (r < l) {
		r += curn;
	}
	int cnt = r - l;
	return ((long long)-cord[l] * cnt % MOD + (cordSum[r + 1] - cordSum[l + 1]) % MOD + MOD) % MOD;
}

int solve(int n, vector<int> &l, vector<int> &c) {
	int ret = 0;
	init(n, l, c);
	for (int i = 0; i < n; ++i) {
		int l = 0, r = n - 1;
		while (l < r) {
			int m = (l + r + 1) >> 1, j = (i + n - m) % n;
			long long d1 = getDis(j, i),
				 	  d2 = c[j] + c[i];
			if (d1 < d2) {
				l = m;
			} else {
				r = m - 1;
			}
		}
		int lc = l;
		l = 0, r = n - 1;
		while (l < r) {
			int m = (l + r + 1) >> 1, j = (i + m) % n;
			long long d1 = getDis(i, j),
				 	  d2 = c[i] + c[j];
			if (d1 < d2) {
				l = m;
			} else {
				r = m - 1;
			}
		}
		int rc = l;
		int lu = (i + n - lc) % n, ru = (i + rc) % n;
		int tmp = 0;
		if (lc + rc == n - 1) {
			tmp = (getDisSum(lu, i) + getDisSumR(i, ru)) % MOD;
		} else if (lc + rc < n - 1) {
			tmp = ((long long) c[i] * (n - 1 - lc - rc) +
							getDisTC((ru + 1) % n, (lu + n - 1) % n) +
						  	getDisSum(lu, i) + getDisSumR(i, ru)) % MOD;
		} else {
			l = 0, r = n - 1;
			while (l < r) {
				int m = (l + r + 1) >> 1, j = (i + m) % n;
				long long d1 = getDis(i, j),
					 	  d2 = getDis(j, i);
				if (d1 < d2) {
					l = m;
				} else {
					r = m - 1;
				}
			}
			rc = l, lc = n - 1 - l;
			lu = (i + n - lc) % n, ru = (i + rc) % n;
			tmp = (getDisSum(lu, i) + getDisSumR(i, ru)) % MOD;
		}
		(ret += tmp) %= MOD;
	}
	return ret;
}

int main() { 
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		--u, --v;
		edge[u].push_back(make_pair(v, w));
		edge[v].push_back(make_pair(u, w));
	}
	msum = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d", m + i);
		--m[i];
		msum += m[i];
		l[i].resize(m[i]), c[i].resize(m[i]);
		for (int j = 0; j < m[i]; ++j) {
			scanf("%d", &l[i][j]);
		}
		for (int j = 0; j < m[i]; ++j) {
			scanf("%d", &c[i][j]);
		}
		for (int _ = 0; _ < 2 * m[i]; ++_) {
			int cur = _ % m[i], pre = (cur + m[i] - 1) % m[i];
			c[i][cur] = min(c[i][cur], c[i][pre] + l[i][pre]);
		}
		for (int _ = 2 * m[i] - 1; _ >= 0; --_) {
			int cur = _ % m[i], nxt = (cur + 1) % m[i];
			c[i][cur] = min(c[i][cur], c[i][nxt] + l[i][cur]);
		}
		tcd[i] = 0;
		for (int j = 0; j < m[i]; ++j) {
			tcd[i] += c[i][j];
			if (tcd[i] >= MOD) {
				tcd[i] -= MOD;
			}
		}
	}
	totcd[0] = dfs(0);
	dfs2(0);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		(ans += ((long long)(totcd[i] - tcd[i]) * m[i] + (long long)tcd[i] * (msum - m[i])) % MOD) %= MOD;
		(ans += solve(m[i], l[i], c[i])) %= MOD;
	}
	printf("%d\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 0ms
memory: 15952kb

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 51 24 86 73 48 97 24
39 91 60 48 18 40 86 86 21
13
45 36 26 43 80 45 19 93 92 70 54 26
69 16 35 12 53 96 97 16 34 98 48 11
11
63 9 62 36 96 68 75 57 73 95
12 78 26 69 77 40 32 2 61 85
11
56 8 94 81 56...

output:

1956394

result:

ok single line: '1956394'

Test #2:

score: 10
Accepted
time: 2ms
memory: 18056kb

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 507 771 95 845 535
21
227 364 845 551 624 386 273 248 497 624 145 736 626 43 680 245 819 693 992 670
395 739 591 160 948 218 540 386 886 421 969 916 535 12 153 296 397 816 34 398
25
554 826 663 809 762 ...

output:

15675138

result:

ok single line: '15675138'

Test #3:

score: 10
Accepted
time: 14ms
memory: 17216kb

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
14 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 60806854...

output:

453173522

result:

ok single line: '453173522'

Test #4:

score: 10
Accepted
time: 142ms
memory: 27912kb

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
14 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 6080685...

output:

181864911

result:

ok single line: '181864911'

Test #5:

score: 10
Accepted
time: 53ms
memory: 21900kb

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 444334906 285277336 710348977 549689938 25501608 262084333 726406198 959644046 180519821 801314662 553615528 939807657 59611169 709779710 127641298 363864144 191485660 406224056 471558685 893843939 1804662...

output:

672785783

result:

ok single line: '672785783'

Test #6:

score: 10
Accepted
time: 234ms
memory: 22428kb

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 355576373 49800966 989990374 194592874 220855926 874351673 294904098 360941450 134202933 266159618 672618225 965819466 368757654 78351396 421404013 402599492 496518662 251795752 630401732 724482117 188...

output:

5175380

result:

ok single line: '5175380'

Test #7:

score: 10
Accepted
time: 173ms
memory: 19944kb

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 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 60806854
2...

output:

691155161

result:

ok single line: '691155161'

Test #8:

score: 10
Accepted
time: 208ms
memory: 19932kb

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
14 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 60806854
...

output:

265274205

result:

ok single line: '265274205'

Test #9:

score: 10
Accepted
time: 221ms
memory: 21068kb

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
14 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 60806854...

output:

682655928

result:

ok single line: '682655928'

Test #10:

score: 10
Accepted
time: 262ms
memory: 28716kb

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
14 22 110010673
10 23 617819337
20 24 156091746
21 25 899894092
20 26 937186358
14 27 25921154
26 28 590357945
1 29 357571491
21 30 927702197
1 31 130060904
7 32 83454667
6 33 685118025
33 34 6080685...

output:

702441060

result:

ok single line: '702441060'