QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #411613 | #7767. 数据结构 | Terac | 0 | 1353ms | 307820kb | C++14 | 6.4kb | 2024-05-15 16:38:14 | 2024-05-15 16:38:14 |
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 = 1; 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: 25ms
memory: 106620kb
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:
22530221648 1551434412746 2043593513572 916136908202 1149041304048 1930351776826 5627975877317 1741813781164 5497206096345 2186592622 3750422895688 1674542130 6524658548 6568501816645 8480988593454 10287912614914 492570862 2712528038832 2834694279 948024175 4395772262 4221137767 9630829210 863214422...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '22530221648'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 943ms
memory: 296092kb
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 3288575788 3288575788 0 3834750343 3834750343 0 0 4489794361 0 0 5224818790 5224818790 5224818790 5961407442 0 6668272644 0 0 8307321880 0 0 0 0 8340628337 0 0 8340628337 0 8850837817 0 0 9699348101 9699348101 9699348101 0 9699348101 0 9828272482 0 9828272482 9828272482 0 0 101871097...
result:
wrong answer 9th numbers differ - expected: '7615073807', found: '3288575788'
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 471ms
memory: 307820kb
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 172304962 179523849291973 75824457254155 143778236366329 219466451073683 224340027176315 163353112374085 262654242884320 206555771768027 3803430930 1896237350 448431934080 359102756720054 693712416606751 740996329746934 215244492677161 18206270459578 4...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '134313322523733'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1353ms
memory: 300204kb
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:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%