/ tabris /

记录详情

Wrong Answer

/in/foo.cc: In function 'void Dfs(long long int, long long int)':
/in/foo.cc:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<mp[u].size();i++)
                ~^~~~~~~~~~~~~
# 状态 耗时 内存占用
#1 Wrong Answer 15ms 19.309 MiB
#2 Wrong Answer 8ms 19.062 MiB
#3 Wrong Answer 8ms 18.062 MiB
#4 Wrong Answer 15ms 19.316 MiB
#5 Wrong Answer 35ms 20.812 MiB
#6 Wrong Answer 33ms 19.934 MiB
#7 Accepted 13ms 19.812 MiB
#8 Accepted 19ms 21.809 MiB
#9 Wrong Answer 447ms 54.184 MiB
#10 Wrong Answer 492ms 54.184 MiB

代码

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long int
vector<ll>mp[505000];
ll a[505000];
ll L[505000];
ll R[505000];
ll cnt;
void Dfs(ll u,ll from)
{
    L[u]=++cnt;
    for(ll i=0;i<mp[u].size();i++)
    {
        ll v=mp[u][i];
        if(v==from)continue;
        Dfs(v,u);
    }
    R[u]=cnt;
}
/******************************************/
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
ll tree[505000*4];
void pushup(ll rt)
{
    tree[rt]=tree[rt*2]+tree[rt*2+1];
}
void build(ll l,ll r,ll rt)
{
    if(l==r)
    {
        tree[rt]=a[l];
        return ;
    }
    ll m=(l+r)/2;
    build(lson);build(rson);pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(l>=L&&r<=R)
    {
        return tree[rt];
    }
    ll ans=0;
    ll m=(l+r)/2;
    if(L<=m)ans+=query(L,R,lson);
    if(R>m)ans+=query(L,R,rson);
    return ans;
}
/******************************************/
int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        cnt=0;
        ll sum=0;
        for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),mp[i].clear(),sum+=a[i];
        for(ll i=1;i<=n-1;i++)
        {
            ll x,y;scanf("%lld%lld",&x,&y);
            mp[x].push_back(y);
            mp[y].push_back(x);
        }
        ll ans1=0,ans2=sum;
        ll maxn=100000000000000000ll;
        Dfs(1,-1);
        build(1,n,1);
        for(ll i=1;i<=n;i++)
        {
            ll A=query(L[i],R[i],1,n,1);
            ll B=sum-A;
            if(A>B)swap(A,B);
            if(abs(A-B)<maxn)
            {
                maxn=abs(A-B);
                ans1=A;ans2=B;
            }
            if(abs(A-B)==maxn)
            {
                if(ans2<B)
                {
                    ans1=A;
                    ans2=B;
                }
            }
        }
        printf("%lld %lld\n",ans1,ans2);
    }
}

信息

递交者
类型
递交
语言
C++
递交时间
2017-09-18 19:25:36
评测时间
2017-09-18 19:25:36
评测机
分数
128
总耗时
1090ms
峰值内存
54.184 MiB