QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#462605 | #553. 王国 | LXl491214 | 100 ✓ | 30ms | 19076kb | C++14 | 2.9kb | 2024-07-03 22:00:46 | 2024-07-03 22:00:46 |
Judging History
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'