QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71861#4102. 游戏He_RenCompile Error//C++174.5kb2023-01-12 02:06:422023-01-12 02:06:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 02:06:45]
  • 评测
查看
  • [2023-01-12 02:06:42]
  • 提交

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;
}
Source code, Language: C++17

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++/11/array:41,
                 from /usr/include/c++/11/tuple:39,
                 from /usr/include/c++/11/functional:54,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from answer.code:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  245 |     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];
      |                 ^~~~
In file included from /usr/include/c++/11/array:41,
                 from /usr/include/c++/11/tuple:39,
                 from /usr/include/c++/11/functional:54,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from answer.code:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  245 |     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];
      |                            ^~~~
In file included from /usr/include/c++/11/array:41,
                 from /usr/include/c++/11/tuple:39,
                 from /usr/include/c++/11/functional:54,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from answer.code:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  245 |     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;
      |                                  ^~~~
In file included from /usr/include/c++/11/array:41,
                 from /usr/include/c++/11/tuple:39,
                 from /usr/include/c++/11/functional:54,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from answer.code:2:
/usr/include/c++/11/bits/range_access.h:254:5: note: candidates are: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/11/bits/range_access.h:245:5: note:                 ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
  245 |     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;
      |                                            ^~~~
In file included from /usr/include/c++/11/array:41,
                 from /usr/include/c++/11/tuple:39,
                 from /usr/include/c++/11/functional:54,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
          ...
English 繁體中文 简体中文

Server Time: 2024-11-30 05:42:49 | OpenSource Project