QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #468003 | #1163. Another Tree Queries Problem | BINYU | Compile Error | / | / | C++14 | 5.4kb | 2024-07-08 18:40:37 | 2024-07-08 18:40:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
#defien int ll
#define ll long long
ll calc(ll st,ll len,ll k)
{
return (2 * st + len * k - k) * len / 2;
}
struct Segment_Tree
{
#define ls id << 1
#define rs id << 1 | 1
struct node
{
ll len,sum,siz,dep,ad1,ad2,ad3;
}a[4 * N + 5];
void pushdown(int id)
{
int ad1 = a[id].ad1,ad2 = a[id].ad2,ad3 = a[id].ad3;
if(ad1)
{
a[ls].ad1 += ad1;
a[ls].sum += ad1 * a[ls].len;
a[rs].ad1 += ad1;
a[rs].sum += ad1 * a[rs].len;
a[id].ad1 = 0;
}
if(ad2)
{
a[rs].ad2 += ad2;
a[rs].sum += calc(ad2,a[rs].len,ad2);
a[ls].ad2 += ad2;
a[ls].ad1 += a[rs].len * ad2;
a[ls].sum += a[rs].len * ad2 * a[ls].len;
a[ls].sum += calc(ad2,a[ls].len,ad2);
a[id].ad2 = 0;
}
if(ad3)
{
a[ls].ad3 += ad3;
a[ls].sum += ad3 * a[ls].siz;
a[rs].ad3 += ad3;
a[rs].sum += ad3 * a[rs].siz;
a[id].ad3 = 0;
}
}
void build(int id,int l,int r)
{
a[id].len = r - l + 1;
if(l == r)return;
int mid = l + r >> 1;
build(ls,l,mid);build(rs,mid + 1,r);
}
void update(int id,int l,int r,int x,ll siz,ll dep)
{
if(l == r)
{
a[id].siz = siz;
a[id].dep = dep;
return;
}
int mid = l + r >> 1;
if(x <= mid)update(ls,l,mid,x,siz,dep);
else update(rs,mid + 1,r,x,siz,dep);
a[id].siz = a[ls].siz + a[rs].siz;
a[id].dep = a[ls].dep + a[rs].dep;
}
void add1(int id,int l,int r,int st,int en,ll v)
{
if(l >= st&&r <= en)
{
a[id].ad1 += v;
a[id].sum += v * (r - l + 1);
return;
}
int mid = l + r >> 1;pushdown(id);
if(st <= mid)add1(ls,l,mid,st,en,v);
if(en > mid)add1(rs,mid + 1,r,st,en,v);
a[id].sum = a[ls].sum + a[rs].sum;
}
int add2(int id,int l,int r,int st,int en,ll v)
{
if(l >= st&&r <= en)
{
a[id].ad1 += v - 1;
a[id].ad2++;
a[id].sum += calc(v,r - l + 1,1);
return v + r - l + 1;
}
int mid = l + r >> 1;pushdown(id);
if(en > mid)v = add2(rs,mid + 1,r,st,en,v);
if(st <= mid)v = add2(ls,l,mid,st,en,v);
a[id].sum = a[ls].sum + a[rs].sum;
return v;
}
void add3(int id,int l,int r,int st,int en,ll v)
{
if(l >= st&&r <= en)
{
a[id].ad3 += v;
a[id].sum += v * a[id].siz;
return;
}
int mid = l + r >> 1;pushdown(id);
if(st <= mid)add3(ls,l,mid,st,en,v);
if(en > mid)add3(rs,mid + 1,r,st,en,v);
a[id].sum = a[ls].sum + a[rs].sum;
}
ll query(int id,int l,int r,int st,int en)
{
if(l >= st&&r <= en)return a[id].sum;
int mid = l + r >> 1;pushdown(id);
ll res = 0;
if(st <= mid)res += query(ls,l,mid,st,en);
if(en > mid)res += query(rs,mid + 1,r,st,en);
return res;
}
int query_dep(int id,int l,int r,int st,int en)
{
if(l >= st&&r <= en)return a[id].dep;
int mid = l + r >> 1;pushdown(id);
ll res = 0;
if(st <= mid)res += query_dep(ls,l,mid,st,en);
if(en > mid)res += query_dep(rs,mid + 1,r,st,en);
return res;
}
#undef ls
#undef rs
}st;
int n,q,u,v,op;
int siz[N + 5],son[N + 5],dep[N + 5],f[20][N + 5];
int dfn[N + 5],cntdfn,top[N + 5];
vector <int> e[N + 5];
ll sum1,sum2;
void dfs1(int u,int fa)
{
siz[u] = 1;
f[0][u] = fa;
dep[u] = dep[fa] + 1;
for(auto v : e[u])
{
if(v == fa)continue;
dfs1(v,u);siz[u] += siz[v];
if(siz[v] > siz[son[u]])
son[u] = v;
}
}
void dfs2(int u,int t)
{
top[u] = t;
dfn[u] = ++cntdfn;
if(son[u])dfs2(son[u],t);
for(auto v : e[u])
if(!dfn[v])dfs2(v,v);
}
int lca(int u,int v)
{
if(dep[u] < dep[v])swap(u,v);
for(int i = 18;~i;i--)
if(dep[f[i][u]] >= dep[v])
u = f[i][u];
if(u == v)return u;
for(int i = 18;~i;i--)
if(f[i][u] != f[i][v])
u = f[i][u],v = f[i][v];
return f[0][u];
}
int jmp(int u,int d)
{
for(int i = 18;~i;i--)
{
if(dep[f[i][u]] > d)
u = f[i][u];
}
return u;
}
ll query(int u)
{
ll res = 0;
while(u)
res += st.query(1,1,n,dfn[top[u]],dfn[u]),
u = f[0][top[u]];
return res;
}
void add1(int u,ll v)
{
while(u)
st.add1(1,1,n,dfn[top[u]],dfn[u],v),
u = f[0][top[u]];
}
void add2(int u,int F)
{
sum1 += dep[u] - dep[F] + 1;
int now = 1;
while(top[u] != top[F])
sum2 += st.query_dep(1,1,n,dfn[top[u]],dfn[u]),
now = st.add2(1,1,n,dfn[top[u]],dfn[u],now),
u = f[0][top[u]];
sum2 += st.query_dep(1,1,n,dfn[F],dfn[u]);
st.add2(1,1,n,dfn[F],dfn[u],now);
}
void add3(int u,ll v)
{
sum1 += v * siz[u];
sum2 += v * st.query_dep(1,1,n,dfn[u],dfn[u] + siz[u] - 1);
st.add3(1,1,n,dfn[u],dfn[u] + siz[u] - 1,v);
add1(f[0][u],v * siz[u]);
}
signed main()
{
scanf("%lld",&n);
for(int i = 1;i < n;i++)
scanf("%lld %lld",&u,&v),
e[u].push_back(v),e[v].push_back(u);
dfs1(1,0);dfs2(1,1);
for(int i = 0;i < 18;i++)
for(int j = 1;j <= n;j++)
f[i + 1][j] = f[i][f[i][j]];
st.build(1,1,n);
for(int i = 1;i <= n;i++)
st.update(1,1,n,dfn[i],siz[i],dep[i]);
scanf("%lld",&q);
while(q--)
{
scanf("%lld",&op);
if(op == 1)
{
scanf("%lld %lld",&u,&v);
if(u == v)add3(1,1);
else if(lca(u,v) == v)
add3(1,1),add3(jmp(u,dep[v]),-1);
else add3(v,1);
}
else if(op == 2)
{
scanf("%lld %lld",&u,&v);
int F = lca(u,v);
sum2 += dep[F];sum1++;
if(F != u)add2(u,jmp(u,dep[F]));
if(F != v)add2(v,jmp(v,dep[F]));
int cnt = dep[u] + dep[v] - 2 * dep[F] + 1;
add1(F,cnt);
}
else
{
scanf("%lld",&u);
ll sum3 = query(u);
cout<<sum1 * dep[u] + sum2 - 2 * sum3<<"\n";
}
}
}
/*
7
2 1
3 2
4 2
5 1
6 4
7 6
2
2 2 7
3 4
*/
Details
answer.code:4:2: error: invalid preprocessing directive #defien; did you mean #define?
4 | #defien int ll
| ^~~~~~
| define
answer.code: In function ‘int main()’:
answer.code:212:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
212 | scanf("%lld",&n);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:214:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
214 | scanf("%lld %lld",&u,&v),
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:214:32: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int*’ [-Wformat=]
214 | scanf("%lld %lld",&u,&v),
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:223:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
223 | scanf("%lld",&q);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:226:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
226 | scanf("%lld",&op);
| ~~~^ ~~~
| | |
| | int*
| long long int*
| %d
answer.code:229:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
229 | scanf("%lld %lld",&u,&v);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:229:40: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int*’ [-Wformat=]
229 | scanf("%lld %lld",&u,&v);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:237:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
237 | scanf("%lld %lld",&u,&v);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:237:40: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int*’ [-Wformat=]
237 | scanf("%lld %lld",&u,&v);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:247:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
247 | scanf("%lld",&u);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
answer.code:212:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
212 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
answer.code:214:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
214 | scanf("%lld %lld",&u,&v),
| ~~~~~^~~~~~~~~~~~~~~~~~~
answer.code:223:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
223 | scanf("%lld",&q);
| ~~~~~^~~~~~~~~~~
answer.code:226:22: warning: ignoring return value of ...