QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368760#7791. 通道建设 Passage ConstructionNATURAL6Compile Error//C++174.1kb2024-03-27 16:09:162024-03-27 16:15:50

Judging History

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

  • [2024-03-27 16:15:50]
  • 评测
查看
  • [2024-03-27 16:09:16]
  • 提交

answer

#include <bits/stdc++.h>
#include "passageconstruction.h"
using namespace std;
int n,dep[10010],mdep,dfn[10010],tot,fa[14][10010],siz[20010];
int node_siz,edge_siz,id[10010],nowdep,vis[20010],msiz,eid,eU,eV;
vector<int>S[10010],e[10010],E[10010];
vector< pair<int,int> >ans,se[20010];
inline void adde(int x,int y)
{
	e[x].emplace_back(y);
	fa[0][y]=x;
	for(int i=1;i<14;++i)fa[i][y]=fa[i-1][fa[i-1][y]];
	return ;
}
inline int get_lca(int x,int y)
{
	if(x==y)return x;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=13;~i;--i)while(dep[fa[i][x]]>=dep[y])x=fa[i][x];
	if(x==y)return x;
	for(int i=13;~i;--i)while(fa[i][x]^fa[i][y])x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}
inline void dfs(int rt)//求 dfs 序
{
	dfn[rt]=++tot;
	for(int i:e[rt])dfs(i);
	return ;
}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
inline void build(vector<int>S)
{
	for(int i=1;i<=(int)S.size();++i)nowpos[i]=0;
	sort(S.begin(),S.end(),cmp);
	for(int i=(int)S.size()-1;i;--i)S.emplace_back(get_lca(S[i],S[i-1]));
	sort(S.begin(),S.end(),cmp);S.resize(unique(S.begin(),S.end())-S.begin());
	for(int i=1;i<(int)S.size();++i)E[get_lca(S[i],S[i-1])].emplace_back(S[i]);
	return S[0];
}
inline int dfss(int rt,int da)// 三度化
{
	if(E[rt].empty())return id[++node_siz]=rt,node_siz;
	if(E[rt].size()==1)
	{
		int U=++node_siz,V=dfss(E[rt][0],rt);
		id[U]=rt;++edge_siz;
		se[U].emplace_back(make_pair(V,edge_siz));
		se[V].emplace_back(make_pair(U,edge_siz));
		return U;
	}
	else
	{
		int V=dfss(E[rt].back(),rt);
		for(int i=E[rt].size()-2;~i;--i)
		{
			int rot=++node_size,U=dfss(E[rt][i],rt);
			++edge_siz;
			e[rot].emplace_back(make_pair(U,edge_siz));
			e[U].emplace_back(make_pair(rot,edge_siz));
			++edge_siz;
			e[rot].emplace_back(make_pair(V,edge_siz));
			e[V].emplace_back(make_pair(rot,edge_siz));
			U=rot;id[rot]=rt;
		}
		return U;
	}
	return 0;
}
inline int get_id(int rt,int da)
{
	if(dep[id[rt]]==nowdep)return id[rt];
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		return get_id(i.first,rt);
	}
	return 0;
}
inline void findroot(int rt,int da,int SZ)
{
	if(dep[id[rt]]==nowdep)siz[rt]=1;
	else siz[rt]=0;
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		findroot(i.first,rt,SZ);siz[rt]+=i.first;
		if(msiz>max(siz[i.first],SZ-siz[i.first]))msiz=max(siz[i.first],SZ-siz[i.first]),eU=rt,eV=i.first,eid=i.second;
	}
	return ;
}
inline int dfssss(int rt,int da)
{
	int an=(dep[id[rt]]==nowdep);
	for(pair<int,int>i:se[rt])
	{
		if(i.first==da||vis[i.second])continue;
		an+=dfssss(i.first,rt);
	}
	return an;
}
inline void dfz(int rt,int SZ,vector<int>nodeset)
{
	if(!SZ||nodeset.empty())return ;
	if(SZ==1)
	{
		int ID=get_id(rt,0);
		for(int i:nodeset)adde(ID,i);
		return ;
	}
	msiz=SZ+1;
	findroot(rt,0,SZ);
	vis[eid]=1;
	int sizU=dfssss(eU,eV),sizV=dfssss(eV,eU);
	vector<int>res,B,toU,toV;B.emplace_back(id[eU]);
	for(pair<int,int>i:se[eU])
	{
		if(i.first==eV||vis[i.second])continue;
		B.emplace_back(id[i.first]);
	}
	if(B.size()==1)res.resize(nodeset.size(),1);
	else res=QueryLCA(nodeset,B,id[eU]);
	for(int i=0;i<(int)nodeset.size();++i)
	{
		if(res[i])toU.emplace_back(nodeset[i]);
		else toV.emplace_back(nodeset[i]);
	}
	int eeU=eU,eeV=eV;
	dfz(eeU,sizU,toU);dfz(eeV,sizV,toV);
	return ;
}
inline void solve(int D)
{
	if(D>=2)for(int i:S[D-2])E[i].clear();
	for(int i=1;i<=node_siz;++i)se[i].clear();
	node_siz=edge_siz=0;
	int rot=build(S[D-1]);
	rot=dfs(rot);
	nowdep=D-1;
	dfz(rot,node_siz,S[D]);
	tot=0;dfs(1);
	return ;
}
inline int dfsss(int rt)\\ 求匹配
{
	int son=0;
	for(int i:e[rt])
	{
		int p=dfsss(i);
		if(p)
		{
			if(son)
			{
				ans.emplace_back(make_pair(p,son));
				son=0;
			}
			else son=p;
		}
	}
	if(son)
	{
		ans.emplace_back(make_pair(rt,son));
		son=0;
	}
	else son=rt;
	return son;
}
vector< pair<int,int> >ConstructPassages(int N,const vector< pair<int,int> >&E)
{
	n=N;
	for(int i=2;i<=(n<<1);++i)
	{
		S[dep[i]=GetDistance(1,i)].emplace_back(i);
		mdep=max(mdep,dep[i]);
	}
	S[0].emplace_back(1);dfn[1]=tot=1;
	for(int i=1;i<=mdep;++i)solve(i);
	dfsss(1);
	return ans;
}
Source code, Language: C++17

Details 

answer.code:143:25: error: stray ‘\’ in program
  143 | inline int dfsss(int rt)\\ 求匹配
      |                         ^
answer.code:143:26: error: stray ‘\’ in program
  143 | inline int dfsss(int rt)\\ 求匹配
      |                          ^
answer.code: In function ‘void build(std::vector<int>)’:
answer.code:33:42: error: ‘nowpos’ was not declared in this scope
   33 |         for(int i=1;i<=(int)S.size();++i)nowpos[i]=0;
      |                                          ^~~~~~
answer.code:38:19: error: return-statement with a value, in function returning ‘void’ [-fpermissive]
   38 |         return S[0];
      |                   ^
answer.code: In function ‘int dfss(int, int)’:
answer.code:56:35: error: ‘node_size’ was not declared in this scope; did you mean ‘node_siz’?
   56 |                         int rot=++node_size,U=dfss(E[rt][i],rt);
      |                                   ^~~~~~~~~
      |                                   node_siz
answer.code:58:55: error: ‘U’ was not declared in this scope
   58 |                         e[rot].emplace_back(make_pair(U,edge_siz));
      |                                                       ^
answer.code:65:24: error: ‘U’ was not declared in this scope
   65 |                 return U;
      |                        ^
answer.code: In function ‘void solve(int)’:
answer.code:136:22: error: void value not ignored as it ought to be
  136 |         int rot=build(S[D-1]);
      |                 ~~~~~^~~~~~~~
answer.code:137:16: error: void value not ignored as it ought to be
  137 |         rot=dfs(rot);
      |             ~~~^~~~~
answer.code: At global scope:
answer.code:143:28: error: expected initializer before ‘求匹配’
  143 | inline int dfsss(int rt)\\ 求匹配
      |                            ^~~~~~
answer.code: In function ‘std::vector<std::pair<int, int> > ConstructPassages(int, const std::vector<std::pair<int, int> >&)’:
answer.code:177:9: error: ‘dfsss’ was not declared in this scope; did you mean ‘dfssss’?
  177 |         dfsss(1);
      |         ^~~~~
      |         dfssss
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/c++allocator.h:33,
                 from /usr/include/c++/13/bits/allocator.h:46,
                 from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:1:
/usr/include/c++/13/bits/new_allocator.h: In instantiation of ‘void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = int; _Args = {std::pair<int, int>}; _Tp = int]’:
/usr/include/c++/13/bits/alloc_traits.h:537:17:   required from ‘static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {std::pair<int, int>}; _Tp = int; allocator_type = std::allocator<int>]’
/usr/include/c++/13/bits/vector.tcc:117:30:   required from ‘std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {std::pair<int, int>}; _Tp = int; _Alloc = std::allocator<int>; reference = int&]’
answer.code:61:23:   required from here
/usr/include/c++/13/bits/new_allocator.h:187:11: error: cannot convert ‘std::pair<int, int>’ to ‘int’ in initialization
  187 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
English 繁體中文 简体中文

Server Time: 2024-12-05 08:27:11 | OpenSource Project