QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #130070 | #329. 点分治 | c20231020# | Compile Error | / | / | C++23 | 1.7kb | 2023-07-23 15:44:00 | 2023-07-23 15:44:03 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-23 15:44:03]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-07-23 15:44:00]
- 提交
answer
#include<bits/stdc++.h>
#define ll int
const ll N=1000010;
using namespace std;
ll n,m,k,cnt,nxt[N],v[N],w[N],fir[N];
ll tot,root,ans;
ll dep[N]; //到根节点的距离
ll dis[N]; //辅助计算总距离
ll vis[N]; //标记是否被删除
ll dp[N]; //子树最大节点数
ll size[N];//此子树节点个数
void add(ll u1,ll v1,ll w1){//加边
v[++cnt]=v1;
w[cnt]=w1;
nxt[cnt]=fir[u1];
fir[u1]=cnt;
}
void getroot(ll x,ll fa,ll sum){//找重心
dp[x]=0;
size[x]=1;
for(ll i=fir[x];i;i=nxt[i]){
if(v[i]!=fa&&!vis[v[i]]){
getroot(v[i],x,sum);
size[x]+=size[v[i]];
dp[x]=max(dp[x],size[v[i]]);
}
}
dp[x]=max(dp[x],sum-size[x]);
if(dp[x]<dp[root])root=x;
}
void getdis(ll x,ll fa){//计算距离
dep[++tot]=dis[x];
for(ll i=fir[x];i;i=nxt[i]){
if(v[i]!=fa&&!vis[v[i]]){
dis[v[i]]=dis[x]+w[i];
getdis(v[i],x);
}
}
}
void getans(ll x,ll p,ll v){//经过x点的路径数
dis[x]=p;
tot=0;
getdis(x,0);
sort(dep+1,dep+tot+1);
ll s=0,l=1,r=tot;
while(l<r){
if(dep[l]+dep[r]<=k){
if(dep[l]+dep[r]==k){
s+=r-(lower_bound(dep+l,dep+r+1,dep[r])-dep)+1;
}
l++;
}else{
r--;
}
}
ans+=s*v;
}
void solve(ll x){//点分治
getans(x,0,1);
vis[x]=1;
for(ll i=fir[x];i;i=nxt[i]){
if(!vis[v[i]]){
getans(v[i],w[i],-1);
root=0;
getroot(v[i],x,size[v[i]]);
solve(root);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(ll i=1;i<n;i++){
ll u1,v1,w1;
scanf("%d%d%d",&u1,&v1,&w1);
add(u1,v1,w1);
add(v1,u1,w1);
}
while(m--){
memset(vis,0,sizeof(vis));
dp[0]=n;
ans=0;
scanf("%d",&k);
getroot(1,0,n);
solve(root);
if(ans)printf("Yes\n");
else printf("No\n");
}
return 0;
}
详细
answer.code: In function ‘void getroot(int, int, int)’:
answer.code:23:9: error: reference to ‘size’ is ambiguous
23 | size[x]=1;
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/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:12:4: note: ‘int size [1000010]’
12 | ll size[N];//此子树节点个数
| ^~~~
answer.code:27:25: error: reference to ‘size’ is ambiguous
27 | size[x]+=size[v[i]];
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/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:12:4: note: ‘int size [1000010]’
12 | ll size[N];//此子树节点个数
| ^~~~
answer.code:27:34: error: reference to ‘size’ is ambiguous
27 | size[x]+=size[v[i]];
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/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:12:4: note: ‘int size [1000010]’
12 | ll size[N];//此子树节点个数
| ^~~~
answer.code:28:41: error: reference to ‘size’ is ambiguous
28 | dp[x]=max(dp[x],size[v[i]]);
| ^~~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/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> con...