QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #393735 | #4102. 游戏 | Ecec243 | Compile Error | / | / | C++23 | 4.5kb | 2024-04-19 10:31:37 | 2024-04-19 10:31:37 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
struct Edge
{
int next,to,w;
}e[MAXN<<1];
int head[MAXN],etot=0;
inline void add(int u,int v,int w)
{
e[++etot] = (Edge){ head[u],v,w};
head[u]=etot;
}
template<typename Line,const int MAXN>
struct Segment_Tree
{
Line *p[MAXN<<2];
ll mn[MAXN<<2];
int n;
#define ls(u) ((u)<<1)
#define rs(u) ((u)<<1|1)
#define lson(u) ls(u),l,mid
#define rson(u) rs(u),mid+1,r
inline void push_up(int u,int l,int r){ mn[u] = min(p[u] -> calc(l,r), min(mn[ls(u)], mn[rs(u)]));}
void build(int n_,Line &k){ n=n_; build(1,1,n,&k);}
void build(int u,int l,int r,Line *k)
{
p[u] = k; mn[u] = p[u] -> calc(l,r);
if(l==r) return;
int mid = (l+r)>>1;
build(lson(u),k); build(rson(u),k);
}
void update(int ql,int qr,Line &k){ update(1,1,n,ql,qr,&k);}
void update(int u,int l,int r,int ql,int qr,Line *k)
{
if(ql<=l && r<=qr)
{
mn[u] = min(mn[u], k -> calc(l,r));
bool wl = k -> calc(l) < p[u] -> calc(l), wr = k -> calc(r) < p[u] -> calc(r);
if(wl && wr){ p[u] = k; return;}
if(!wl && !wr) return;
int mid = (l+r)>>1;
if(k -> calc(mid) < p[u] -> calc(mid))
{
if(k -> k < p[u] -> k) update(lson(u),ql,qr,p[u]);
else update(rson(u),ql,qr,p[u]);
p[u] = k;
}
else
{
if(k -> k < p[u] -> k) update(rson(u),ql,qr,k);
else update(lson(u),ql,qr,k);
}
return;
}
int mid = (l+r)>>1;
if(ql<=mid) update(lson(u), ql,qr,k);
if(mid<qr) update(rson(u), ql,qr,k);
push_up(u,l,r);
}
ll query(int q){ return query(1,1,n,q);}
ll query(int u,int l,int r,int q)
{
if(l==r) return mn[u];
int mid = (l+r)>>1;
if(q<=mid) return min(p[u] -> calc(q), query(lson(u),q));
else return min(p[u] -> calc(q), query(rson(u),q));
}
ll query(int ql,int qr){ return query(1,1,n,ql,qr);}
ll query(int u,int l,int r,int ql,int qr)
{
if(ql<=l && r<=qr) return mn[u];
int mid = (l+r)>>1; ll res = p[u] -> calc(max(ql,l), min(qr,r));
if(ql<=mid) res = min(res, query(lson(u),ql,qr));
if(mid<qr) res = min(res, query(rson(u),ql,qr));
return res;
}
};
int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
ll dis[MAXN];
void dfs_size(int u,int fa)
{
size[u]=1; son[u]=-1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].to;
if(v==fa) continue;
dep[v] = dep[u] + 1; dis[v] = dis[u] + e[i].w;
pre[v] = u; prew[v] = e[i].w;
dfs_size(v,u);
size[u] += size[v];
if(son[u]==-1 || size[v] > size[son[u]]) son[u] = v;
}
}
int dfn[MAXN], seq[MAXN], cur = 0, top[MAXN];
void dfs_dfn(int u,int fa,int tp)
{
dfn[u] = ++cur; seq[cur] = u;
top[u] = tp;
if(son[u] == -1) return;
dfs_dfn(son[u],u, tp);
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].to;
if(v==fa || v==son[u]) continue;
dfs_dfn(v,u,v);
}
}
int lca(int u,int v)
{
while(top[u] != top[v])
if(dep[top[u]] > dep[top[v]]) u = pre[top[u]];
else v = pre[top[v]];
return dep[u] > dep[v]? v: u;
}
ll cor[MAXN];
struct Line
{
int k;
ll b;
Line(int k=0,ll b=0): k(k), b(b) {}
Line(int i,ll beg,int kk): k(-kk), b(beg + cor[i] * kk) {}
inline ll calc(int x){ return k * cor[x] + b;}
inline ll calc(int l,int r){ return k<0? calc(r): calc(l);}
};
Segment_Tree<Line,MAXN> tree;
void update(int u,int v, ll beg,int k)
{
while(top[u] != top[v])
{
tree.update(dfn[top[u]], dfn[u], *new Line(dfn[u],beg,k));
beg += (dis[u] - dis[pre[top[u]]]) * k;
u = pre[top[u]];
}
tree.update(dfn[v], dfn[u], *new Line(dfn[u],beg,k));
}
ll query(int u,int v)
{
ll res = 123456789123456789;
while(top[u] != top[v])
{
res = min(res, tree.query(dfn[top[u]], dfn[u]));
u = pre[top[u]];
}
return min(res, tree.query(dfn[v], dfn[u]));
}
int main(void)
{
int n,Q;
scanf("%d%d",&n,&Q);
for(int i=1; i<n; ++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfs_size(1,0);
dfs_dfn(1,0,1);
for(int i=1; i<=n; ++i)
{
int u = seq[i];
if(u == top[u]) cor[i] = cor[i-1] + 1;
else cor[i] = cor[i-1] + prew[u];
}
tree.build(n,*new Line(0,123456789123456789));
while(Q--)
{
int oper,u,v;
scanf("%d%d%d",&oper,&u,&v);
if(oper==1)
{
int a,b;
scanf("%d%d",&a,&b);
int uv = lca(u,v);
update(u,uv,b,a); update(v,uv,(dis[u] + dis[v] - 2 * dis[uv]) * a + b,-a);
}
else
{
int uv = lca(u,v);
printf("%lld\n",min(query(u,uv), query(v,uv)));
}
}
return 0;
}
Details
answer.code: In function ‘void dfs_size(int, int)’:
answer.code:91:9: error: reference to ‘size’ is ambiguous
91 | size[u]=1; son[u]=-1;
| ^~~~
In file included from /usr/include/c++/13/vector:69,
from answer.code:3:
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:87:16: note: ‘int size [100005]’
87 | int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
| ^~~~
answer.code:99:17: error: reference to ‘size’ is ambiguous
99 | size[u] += size[v];
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:87:16: note: ‘int size [100005]’
87 | int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
| ^~~~
answer.code:99:28: error: reference to ‘size’ is ambiguous
99 | size[u] += size[v];
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:87:16: note: ‘int size [100005]’
87 | int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
| ^~~~
answer.code:100:34: error: reference to ‘size’ is ambiguous
100 | if(son[u]==-1 || size[v] > size[son[u]]) son[u] = v;
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:87:16: note: ‘int size [100005]’
87 | int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
| ^~~~
answer.code:100:44: error: reference to ‘size’ is ambiguous
100 | if(son[u]==-1 || size[v] > size[son[u]]) son[u] = v;
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
answer.code:87:16: note: ‘int size [100005]’
87 | int dep[MAXN], size[MAXN], son[MAXN], pre[MAXN], prew[MAXN];
| ^~~~
answer.code: In function ‘int main()’:
answer.code:166:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
166 | scanf("%d%d",&n,&Q);
| ~~~~~^~~~~~~~~~~~~~
answer.code:170:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
170 | scanf("%d%d%d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
answer.code:189:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
189 | scanf("%d%d%d",&oper,&u,&v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
answer.code:193:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unus...