QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411617 | #7767. 数据结构 | Terac | 10 | 1521ms | 354476kb | C++14 | 6.4kb | 2024-05-15 16:40:17 | 2024-05-15 16:40:17 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
#define ull unsigned long long
using namespace std;
namespace IO {
#if ONLINE_JUDGE
#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
#else
#define getc() getchar()
#endif
const int IL = 1 << 21, OL = 1 << 21;
int olen = 0;
char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
inline int read() {
register char ch = getc(); register int x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
return x * f;
}
inline double readdb() {
register char ch = getc(); register double x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
if(ch == '.') {
register double b = 0.1;
ch = getc();
while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
}
return x * f;
}
inline int readstr(char *s) {
register char ch = getc(); register int len = 0;
while(!isalpha(ch)) ch = getc();
while(isalpha(ch)) s[++len] = ch, ch = getc();
return len;
}
inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
inline void putc(register char ch) { obuf[olen++] = ch; }
template<class T>
inline void write(register T x) {
if(x < 0) obuf[olen++] = '-', x = -x;
if(x > 9) write(x / 10);
obuf[olen++] = x % 10 + 48;
}
} using namespace IO;
const int N = 2e5 + 10;
int n, k, q, tim;
int fa[N], dep[N], siz[N], dfn[N], id[N], top[N];
namespace bit {
ull t1[N], t2[N];
void add1(int x, ull k) {
for(int i = x; i <= n; i += i & -i)
t1[i] += k;
}
void add2(int x, ull k) {
for(int i = x; i <= n; i += i & -i)
t2[i] += k;
}
ull qry1(int x) {
ull res = 0;
for(int i = x; i; i -= i & -i)
res += t1[i];
return res;
}
ull qry2(int x) {
ull res = 0;
for(int i = x; i; i -= i & -i)
res += t2[i];
return res;
}
ull qry(int l, int r) {
return qry2(r) * r + qry1(r) - qry2(l - 1) * (l - 1) - qry1(l - 1);
}
void add(int l, int r, ull k) {
// cout << "add:" << l << " " << r << " " << k << endl;
add1(l, -k * (l - 1)), add1(r + 1, k * r);
add2(l, k), add2(r + 1, -k);
// cout << qry(1, 7) << endl;
}
} using namespace bit;
vector<int> E[N], e[N];
vector<pii> son[N][4], ans[N][4], fk[N][4], lf[N][4], st[N];
bool cmp(int x, int y) { return siz[x] > siz[y]; }
void dfs1(int u, int f) {
fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
for(auto v : E[u]) {
if(v == f) continue;
e[u].push_back(v);
dfs1(v, u);
siz[u] += siz[v];
}
sort(e[u].begin(), e[u].end(), cmp);
}
void merge(vector<pii> &x) {
vector<pii> vc;
sort(x.begin(), x.end());
for(auto r : x) {
if(vc.size() && r.fir == vc.back().sec + 1) vc[vc.size() - 1].sec = r.second;
else vc.push_back(r);
}
x = vc;
}
void merge(vector<pii> &x, vector<pii> y) {
for(auto r : y) x.push_back(r);
merge(x);
}
void nt(int u, int d) {
if(!d) {
if(!dfn[u]) dfn[u] = ++tim, id[tim] = u;
return;
}
for(auto v : e[u]) nt(v, d - 1);
}
void dfs2(int u) {
vector<int> vc;
int v = u;
while(1) {
top[v] = u;
if(!dfn[v]) dfn[v] = ++tim, id[tim] = v;
vc.push_back(v);
if(!e[v].size()) break;
v = e[v][0];
}
for(int i = 1; i <= k; i++)
for(auto x : vc)
nt(x, i);
for(int i = vc.size() - 1; ~i; i--)
for(int j = 1; j < e[vc[i]].size(); j++)
dfs2(e[vc[i]][j]);
}
void dfs3(int u) {
son[u][0].push_back({dfn[u], dfn[u]});
st[u].push_back({dfn[u], dfn[u]});
for(auto v : e[u]) {
dfs3(v);
merge(st[u], st[v]);
for(int i = 0; i <= k; i++)
merge(fk[v][i], son[u][i]);
for(int i = 1; i <= k; i++)
merge(son[u][i], son[v][i - 1]);
}
vector<pii> tmp[11];
for(int i = e[u].size() - 1, v; ~i; i--) {
v = e[u][i];
for(int i = 1; i <= k; i++)
merge(fk[v][i], tmp[i]);
for(int i = 1; i <= k; i++)
merge(tmp[i], son[v][i - 1]);
}
}
void dfs4(int u) {
ans[u][0].push_back({dfn[u], dfn[u]});
for(int i = 0; i <= k; i++)
lf[u][i] = lf[fa[u]][i];
if(u == 1) {
lf[u][0] = son[u][0];
for(int i = 1; i <= k; i++)
lf[u][i] = lf[u][i - 1], merge(lf[u][i], son[u][i]);
}
else
for(int i = 0; i <= k; i++)
merge(lf[u][i], son[u][i]);
for(int i = 1; i <= k; i++) {
ans[u][i] = son[u][i];
for(int j = 1, f = u; fa[f] && j <= i; f = fa[f], j++)
merge(ans[u][i], fk[f][i - j]);
}
for(auto v : e[u]) dfs4(v);
}
int LCA(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
int main() {
n = read(), q = read();
k = 3;
for(int i = 1; i < n; i++) {
int u = read(), v = read();
E[u].push_back(v);
E[v].push_back(u);
}
dfs1(1, 0);
dfs2(1);
dfs3(1);
dfs4(1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
merge(ans[i][j], ans[i][j - 1]);
// for(int i =1; i <= n;i++)
// cout<< "dfn:" << i << " " << dfn[i] << endl;
// for(int i = 1; i <= n; i++) {
// cout << i << "\n\n";
// for(int j = 0; j <= 0; puts(""), j++)
// for(auto x : lf[i])
// cout << "["<<x.fir << " " << x.sec << "]"<< endl;
// }
// printf("%d\n", query(1, 1, n, dfn[1]));
// for(int i =1; i <= n; puts(""), i++)
// for(auto x : lf[i][3])
// cout << "pos:"<<i<<" " << "["<<x.fir << " "<<x.sec <<"]"<< endl;
while(q--) {
int op = read();
if(op == 1) {
int u = read(), v = read(), k = read(), t = read();
int f = LCA(u, v);
for(auto x : lf[u][k])
add(x.fir, x.sec, t);
for(auto x : lf[v][k])
add(x.fir, x.sec, t);
for(auto x : lf[f][k])
add(x.fir, x.sec, -t);
for(auto x : lf[fa[f]][k])
add(x.fir, x.sec, -t);
}
if(op == 2) {
int u = read(), v = read();
// cout << "!!!:" << st[u].size() << endl;
for(auto x : st[u])
add(x.fir, x.sec, v);
}
if(op == 3) {
int u = read(), v = read(), k = read();
int f = LCA(u, v);
ull ans = 0;
for(auto x : lf[u][k])
ans += qry(x.fir, x.sec);
for(auto x : lf[v][k])
ans += qry(x.fir, x.sec);
for(auto x : lf[f][k])
ans -= qry(x.fir, x.sec);
for(auto x : lf[fa[f]][k])
ans -= qry(x.fir, x.sec);
printf("%llu\n", ans);
}
if(op == 4) {
int u = read();
ull ans = 0;
for(auto x : st[u])
ans += qry(x.fir, x.sec);
printf("%llu\n", ans);
}
}
return 0;
}
/*
7 6
1 2
2 3
1 4
4 5
1 6
6 7
1 1 5 3 4
2 3 5
3 1 5 3
4 5
4 3
4 2
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 20ms
memory: 97772kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
32933561120 2130120170876 2794367845468 1305828665924 1690448429070 2678958746332 6681417865297 2079488841526 5786332239171 2186592622 4014965079076 1674542130 6524658548 7091052607583 10040980978798 11583010045454 492570862 3333441131196 2834694279 4188546805364 4395772262 4221137767 9630829210 989...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '32933561120'
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1226ms
memory: 318720kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 10
Accepted
time: 1302ms
memory: 354476kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 506ms
memory: 305740kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 134313322523733 38210069287857 75885012627846 25202076347900 179523849291973 75824457254155 156951554536901 246507909884129 251381485986761 181645863942433 285463128028270 213787601973331 244899810363137 53370719292672 448431934080 379306317440032 720753875417197 768639337974684 224741669585515 18...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '134313322523733'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1521ms
memory: 324196kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 259th numbers differ - expected: '782172417', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%