QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109030#5418. Color the TreeshihoghmeanCompile Error//C++173.8kb2023-05-27 10:04:462023-05-27 10:04:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-27 10:04:47]
  • 评测
查看
  • [2023-05-27 10:04:46]
  • 提交

answer


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define py puts("Yes")
#define pn puts("No")
#define pt puts("")
#define pb push_back
#define wt(x) write(x),puts("")
#define wr(x) write(x) ,putchar(' ')
#define tx printf("fds")
#define mp make_pair
#define fi first
#define se second
inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*k;
}
void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int power(int x,int y,int mod){
	int num=1;
	while(y){
		if(y&1) num=(num*x)%mod;
		x=x*x%mod;
		y>>=1;
	}
	return num;
}
int mul(int x,int y,int mod){
	int num=0;
	while(y){
		if(y&1) num=(num+x)%mod;
		x=(x+x)%mod;
		y>>=1;
	}
	return num;
}
const int N=1e6+7,mod=998244353;
int n,m,tot,cnt,ans,k;
int a[N];
int head[N];
struct edge{
    int to,next;
}e[N];
void add(int u,int v){
    e[++tot]={v,head[u]};
    head[u]=tot;
}
struct tree{
    int ls,rs;
    int num;
}t[N];
int siz[N],dep[N],son[N],mdep[N],top[N];
int rt[N];
int rmq[N][20];
int newnode(int x){
    t[x]={0,0,0};
    return x;
}
void pu(int id){
    int x=0,y=0;
    if(t[id].ls) x=t[t[id].ls].num;
    if(t[id].rs) y=t[t[id].rs].num;
    t[id].num=x+y;
}
void update(int id,int l,int r,int x,int k){
    if(l==r){
        t[id].num=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        if(!t[id].ls) t[id].ls=newnode(++cnt);
        update(t[id].ls,l,mid,x,k);
    }
    else{
        if(!t[id].rs) t[id].rs=newnode(++cnt);
        update(t[id].rs,mid+1,r,x,k);
    }
    pu(id);
}
int RMQ(int l,int r){
    int x=log2(r-l+1);
    return min(rmq[l][x],rmq[r-(1<<x)+1][x]);
}
int merge(int ddp,int dp,int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(l==r){
        t[x].num=min(t[x].num+t[y].num,RMQ(l-dp+1,l-ddp+1));
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=merge(ddp,dp,t[x].ls,t[y].ls,l,mid);
    t[x].rs=merge(ddp,dp,t[x].rs,t[y].rs,mid+1,r);
    pu(x);
    return x;
}
void dfs(int u,int fa){
    dep[u]=mdep[u]=dep[fa]+1;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        mdep[u]=max(mdep[u],mdep[v]);
        if(mdep[v]>mdep[son[u]]){
            son[u]=v;
        }
    }
}
void dfs1(int u,int fa,int tp){
    top[u]=tp;
    if(u==tp) rt[u]=newnode(++cnt);
    update(rt[top[u]],1,n,dep[u],RMQ(1,dep[u]-dep[top[u]]+1));
    if(son[u]) dfs1(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;
        dfs1(v,u,v);
    }
}
void dfs2(int u,int fa){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs2(v,u);
        if(son[u]!=v) rt[top[u]]=merge(dep[top[u]],dep[u],rt[top[u]],rt[top[v]],1,n);
    }
}
signed main(){
	int tt=read();
	while(tt--){
		tot=0;
        n=read();
        fo(i,1,n) head[i]=0,rt[i]=0,son[i]=0,siz[i]=0,dep[i]=0,mdep[i]=0,top[i]=0;
        fo(i,0,n-1) a[i]=read();
        fo(i,1,n)
            fo(j,0,19) rmq[i][j]=1e9;
        fo(i,1,n){
            rmq[i][0]=a[i-1];
        }
        fo(i,1,19){
            fo(j,1,n){
                rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
            }
        }
        fo(i,2,n){
            int x=read(),y=read();
            add(x,y);
            add(y,x);
        }
        cnt=0;
        dfs(1,0);
        dfs1(1,0,1);
        dfs2(1,0);
        wt(t[rt[1]].num);
	}
	return 0;
}
Source code, Language: C++17

Details 

In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:2:
/usr/include/c++/11/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = long long int; _Iterator2 = long long int; _Compare = long long int]’:
/usr/include/c++/11/bits/stl_algo.h:4888:14:   required from ‘_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = long long int; _InputIterator2 = long long int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<long long int>]’
/usr/include/c++/11/bits/stl_algo.h:4997:37:   required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = long long int; _IIter2 = long long int; _OIter = int; _Compare = long long int]’
answer.code:147:39:   required from here
/usr/include/c++/11/bits/predefined_ops.h:158:31: error: invalid type argument of unary ‘*’ (have ‘long long int’)
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                               ^~~~~~
/usr/include/c++/11/bits/predefined_ops.h:158:39: error: invalid type argument of unary ‘*’ (have ‘long long int’)
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                                       ^~~~~~
/usr/include/c++/11/bits/predefined_ops.h:158:30: error: expression cannot be used as a function
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:2:
/usr/include/c++/11/bits/stl_algo.h: In instantiation of ‘_OutputIterator std::__merge(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = long long int; _InputIterator2 = long long int; _OutputIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<long long int>]’:
/usr/include/c++/11/bits/stl_algo.h:4997:37:   required from ‘_OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = long long int; _IIter2 = long long int; _OIter = int; _Compare = long long int]’
answer.code:147:39:   required from here
/usr/include/c++/11/bits/stl_algo.h:4890:15: error: invalid type argument of unary ‘*’ (have ‘int’)
 4890 |               *__result = *__first2;
      |               ^~~~~~~~~
/usr/include/c++/11/bits/stl_algo.h:4890:27: error: invalid type argument of unary ‘*’ (have ‘long long int’)
 4890 |               *__result = *__first2;
      |                           ^~~~~~~~~
/usr/include/c++/11/bits/stl_algo.h:4895:15: error: invalid type argument of unary ‘*’ (have ‘int’)
 4895 |               *__result = *__first1;
      |               ^~~~~~~~~
/usr/include/c++/11/bits/stl_algo.h:4895:27: error: invalid type argument of unary ‘*’ (have ‘long long int’)
 4895 |               *__result = *__first1;
      |                           ^~~~~~~~~
English 繁體中文 简体中文

Server Time: 2024-12-05 12:41:19 | OpenSource Project