QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#6986 | #553. 王国 | govanitics | 100 ✓ | 262ms | 28716kb | C++98 | 4.4kb | 2021-03-19 13:27:18 | 2021-12-19 10:00:08 |
Judging History
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'