QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #399275 | #943. Dynamic Diameter | sichengzhou# | Compile Error | / | / | C++14 | 5.0kb | 2024-04-26 09:14:12 | 2024-07-04 03:38:24 |
Judging History
This is the latest submission verdict.
- [2024-07-04 03:38:24]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-04-26 09:14:12]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
bool fl=1,pd=1;
typedef long long LL;
const int N=1e5+5;
int n;
priority_queue<LL>q1,q2;
LL t[N<<2],lz[N<<2];
void update(int p)
{
t[p]=max(t[p<<1],t[p<<1|1]);
}
void pushlz(int p,LL z)
{
t[p]+=z;
lz[p]+=z;
}
void lzdown(int p)
{
pushlz(p<<1,lz[p]);
pushlz(p<<1|1,lz[p]);
lz[p]=0;
}
void change(int p,int l,int r,int x,int y,LL z)
{
if(x<=l&&r<=y)
{
pushlz(p,z);
return ;
}
lzdown(p);
int mid=l+r>>1;
if(x<=mid)
{
change(p<<1,l,mid,x,y,z);
}
if(mid+1<=y)
{
change(p<<1|1,mid+1,r,x,y,z);
}
update(p);
}
LL query(int p,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return t[p];
}
int mid=l+r>>1;
LL ret=0;
lzdown(p);
if(x<=mid)
{
ret=max(ret,query(p<<1,l,mid,x,y));
}
if(mid+1<=y)
{
ret=max(ret,query(p<<1|1,mid+1,r,x,y));
}
return ret;
}
struct Edge{
int v,nxt,id;
LL c;
}e[N<<1];
int p[N];
LL edge[N];
int h[N],tot1;
void addEdge(int u,int v,LL c,int id)
{
tot1++;
e[tot1].v=v;e[tot1].nxt=h[u];
e[tot1].c=c;e[tot1].id=id;
h[u]=tot1;
}
int d[N],fa[N],len[N];
LL ans;
void dfs0(int u)
{
int zd=0,cd=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])
{
continue;
}
p[e[i].id]=v;edge[v]=e[i].c;
fa[v]=u;
dfs0(v);
}
}
void add(LL x)
{
// cout<<"add("<<x<<")\n";
q1.push(x);
}
void del(LL x)
{
// cout<<"del("<<x<<")\n";
q2.push(x);
}
LL get_top()
{
// cout<<q1.top()<<'#'<<q2.top()<<endl;
while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top())
{
// cout<<q1.top()<<'^'<<q2.top()<<endl;
q1.pop();q2.pop();
}
// assert(q1.empty()==0);
if(q1.empty())
{
return -1;
}
return q1.top();
}
void calc(int u)
{
d[u]=0;
int zd=0,cd=0;
del(len[u]);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])
{
continue;
}
d[u]=max(d[u],d[v]+edge[v]);
if(zd<d[v]+edge[v])
{
cd=zd;
zd=d[v]+edge[v];
}else if(cd<d[v]+edge[v])
{
cd=d[v]+edge[v];
}
}
len[u]=zd+cd;
add(zd+cd);
}
void dfs(int u)
{
d[u]=0;
int zd=0,cd=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])
{
continue;
}
fa[v]=u;
dfs(v);
d[u]=max(d[u],d[v]+edge[v]);
if(zd<d[v]+edge[v])
{
cd=zd;
zd=d[v]+edge[v];
}else if(cd<d[v]+edge[v])
{
cd=d[v]+edge[v];
}
}
len[u]=zd+cd;
add(len[u]);
}
LL dep[N];
int dfn[N],idx,sz[N],hd[N];
void dfs1(int u)
{
dfn[u]=++idx;sz[u]=1;
change(1,1,n,dfn[u],dfn[u],dep[u]);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])
{
continue;
}
dep[v]=dep[u]+edge[v];
if(u==1)
{
hd[v]=v;
}else{
hd[v]=hd[u];
}
dfs1(v);
sz[u]+=sz[v];
}
}
int main()
{
int u,v,id,Q;
LL w,c;
scanf("%d%d%lld",&n,&Q,&w);
for(int i=1;i<n;i++)
{
scanf("%d%d%lld",&u,&v,&c);
addEdge(u,v,c,i-1);
addEdge(v,u,c,i-1);
if(u>1&&v>1)
{
fl=0;
}
if(u/2!=v&&v/2!=u)
{
pd=0;
}
}
ans=0;
dfs0(1);
bool fl1=(n>5000&&pd==0);
if(0)
{
for(int i=2;i<=n;i++)
{
q1.push(edge[i]);
}
}else if(fl1){
dfs1(1);
for(int i=h[1];i;i=e[i].nxt)
{
int v=e[i].v;
add(query(1,1,n,dfn[v],dfn[v]+sz[v]-1));
}
}else{
dfs(1);
}
ans=0;
while(Q--)
{
scanf("%d%lld",&id,&c);
id+=ans%(n-1);id%=n-1;
c+=ans;c%=w;
if(fl&&0)
{
del(edge[p[id]]);
add(c);
}
if(fl1)
{
int x=hd[p[id]];
del(query(1,1,n,dfn[x],dfn[x]+sz[x]-1));
change(1,1,n,dfn[p[id]],dfn[p[id]]+sz[p[id]]-1,c-edge[p[id]]);
add(query(1,1,n,dfn[x],dfn[x]+sz[x]-1));
}
edge[p[id]]=c;
// cout<<id<<' '<<p[id]<<'*'<<c<<endl;
if(fl1==0){
for(int u=fa[p[id]];u;u=fa[u])
{
calc(u);
}
ans=get_top();
}else{
LL cur=get_top();del(cur);
LL cur1=get_top();
if(cur1==-1)
{
ans=cur;
}else{
ans=cur+cur1;
}
add(cur);
}
printf("%lld\n",ans);
}
return 0;
}
详细
answer.code: In function ‘void calc(int)’:
answer.code:130:17: error: no matching function for call to ‘max(int&, LL)’
130 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/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:130:17: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘LL’ {aka ‘long long int’})
130 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:130:17: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘LL’ {aka ‘long long int’})
130 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/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:130:17: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
130 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:130:17: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
130 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
answer.code: In function ‘void dfs(int)’:
answer.code:156:17: error: no matching function for call to ‘max(int&, LL)’
156 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:156:17: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘LL’ {aka ‘long long int’})
156 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:156:17: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘LL’ {aka ‘long long int’})
156 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:156:17: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
156 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
/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:156:17: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
156 | d[u]=max(d[u],d[v]+edge[v]);
| ~~~^~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:197:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
197 | scanf("%d%d%lld",&n,&Q,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
answer.cod...