QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#154183#7118. Closing Timepaul2008Compile Error//C++144.5kb2023-08-31 14:36:352024-04-28 06:32:23

Judging History

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

  • [2024-04-28 06:32:23]
  • 管理员手动重测本题所有提交记录
查看
  • [2023-08-31 14:36:36]
  • 评测
查看
  • [2023-08-31 14:36:35]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const long long N=4e5+5;

vector <long long> g[N],w[N];
long long fat[N],fa[N],son[N],a[N],n;
long long distx[N],disty[N];
bool inpath[N];

void dfsx(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		fat[to]=x;
		distx[to]=distx[x]+w[x][i];
		dfsx(to,x);
	}
}

void dfsy(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		disty[to]=disty[x]+w[x][i];
		dfsy(to,x);
	}
}

long long calc(long long k)
{
	priority_queue <long long,vector <long long>,greater<long long> > q;
	for(long long i=1;i<=n;i++)
		q.push(distx[i]);

	for(long long i=1;i<=n;i++)
		q.push(disty[i]);

	long long ans=0;
	while(!q.empty())
	{
		long long x=q.top();
		q.pop();
		k -= x, ans++;
		if(k<0)
			return ans-1;
	}
	return ans;
}

void add(long long x,long long y,long long z)
{
	g[x].push_back(y);
	w[x].push_back(z);
}

struct node
{
	long long sz,sum;
	long long id;

	bool operator <(const node& oth) const
	{
		return sum*oth.sz>oth.sum*sz;
	}
}val[N];

bool del[N],in[N];
pair <long long,long long> edge[N];
long long sumfirst[N];
long long cnt;
priority_queue <pair<long long,long long>,vector <pair<long long,long long> >,greater<pair<long long,long long> > > q;

long long gettop()
{
	while(del[q.top().second])
		q.pop();

	in[q.top().second]=true;
	long long ans=q.top().first;
	q.pop();
	return ans;
}

bool check(long long m,long long k) //判断是否可以取m个，上界为k
{
	if(m==cnt*2+1)
		return false;

	while(!q.empty())
		q.pop();

	for(long long i=1;i<=cnt*2;i++)
		del[i]=in[i]=false;

	sort(edge+1,edge+cnt+1);
	for(long long i=1;i<=cnt;i++) //处理第一行的前缀和
		sumfirst[i]=sumfirst[i-1]+edge[i].second;

	for(long long i=1;i<=cnt;i++)
		q.push(make_pair(edge[i].first-edge[i].second,i+cnt)); //第一行的标号为i，第二行的标号为i+cnt

	long long nowsum=0;
	for(long long i=1;i<=m-cnt;i++)
		nowsum += gettop();

	for(long long i=cnt;i>=0;i--) //[1,i]都取了第一行，这些列的决策都为“第二行”，[i+1,n]都不能取第二行，决策为“第一行”
	{ //要维护前m-i小的和
		if(i>m)
			continue;

		if(nowsum+sumfirst[i]<=k) //当前这个i是合法的
			return true;

		if(i+cnt<=m)
			return false;

		//更新nowsum
		q.push(make_pair(edge[i].second,i));
		nowsum += gettop();

		del[i+cnt]=true;
		if(in[i+cnt])
		{
			in[i+cnt]=false;
			nowsum -= edge[i].first-edge[i].second;
			nowsum += gettop();
		}
	}

	return false;
}

void add(long long x,long long y)
{
	edge[++cnt]=make_pair(x+y,x);
}

int max_score(int N, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W)
{
	n=N, x++, y++, cnt=0;
	for(long long i=1;i<=n;i++)
		g[i].clear(), w[i].clear(), inpath[i]=false, distx[i]=disty[i]=fat[i]=0;

	for(long long i=0;i<n-1;i++)
	{
		add(U[i]+1,V[i]+1,W[i]);
		add(V[i]+1,U[i]+1,W[i]);
	}

	dfsx(x,-1), dfsy(y,-1);
	for(long long i=1;i<=n;i++)
		g[i].clear();

	for(long long i=0;i<=n*2;i++)
		fa[i]=son[i]=del[i]=0;

	long long sum=0,cnt=0,ans=calc(k);
	for(long long i=y;i;i=fat[i])
	{
		inpath[i]=true;
		if(distx[i]>disty[i]) swap(distx[i],disty[i]);

		add(0,disty[i]-distx[i]);
		k -= distx[i], sum++;
		val[cnt+1].sum=disty[i]-distx[i];
		cnt++;
	}

	long long realk=k;
	if(k<0)
		return ans;

	for(long long i=1;i<=n;i++)
	{
		if(!inpath[i])
		{
			if(distx[i]>disty[i]) swap(distx[i],disty[i]);

			add(distx[i],disty[i]-distx[i]);
			val[cnt+2].sum=disty[i]-distx[i], val[cnt+1].sum=distx[i];
			fa[cnt+2]=cnt+1, son[cnt+1]=cnt+2;
			cnt += 2;
		}
	}

	priority_queue <node> q;
	for(long long i=1;i<=cnt;i++)
	{
		val[i].sz=1, val[i].id=i;
		q.push(val[i]), a[i]=val[i].sum;
	}

	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(del[x.id])
			continue;

		if(!fa[x.id] || del[fa[x.id]])
		{
			if(k>=x.sum)
			{
				k -= x.sum;
				sum += x.sz;
				if(x.sz==1)
					del[x.id]=true;
				else
					del[x.id]=del[son[x.id]]=true;
				continue;
			}
			else
				break;
		}
		else
		{
			val[fa[x.id]].sz += val[x.id].sz, val[fa[x.id]].sum += x.sum;
			q.push(val[fa[x.id]]);
		}
	}

	for(int i=1;;i++)
		if(!check(i,realk))
			return max(i-1,ans);
}
Source code, Language: C++14

Details 

answer.code: In function ‘int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)’:
answer.code:238:35: error: no matching function for call to ‘max(int, long long int&)’
  238 |                         return max(i-1,ans);
      |                                ~~~^~~~~~~~~
In file included from /usr/include/c++/13/string:51,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:238:35: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
  238 |                         return max(i-1,ans);
      |                                ~~~^~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:238:35: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
  238 |                         return max(i-1,ans);
      |                                ~~~^~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from answer.code:3:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:238:35: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  238 |                         return max(i-1,ans);
      |                                ~~~^~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:238:35: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  238 |                         return max(i-1,ans);
      |                                ~~~^~~~~~~~~
English 繁體中文 简体中文

Server Time: 2024-12-11 18:41:35 | OpenSource Project