求教 20分偏分 为什么过不了三四两个点 十分感谢

KEIONG @ 2017-08-09 11:00:25

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int w[10001];
int s[10001];
int t[10001];
int sum[10001];
int main()
{
    memset(w,127,sizeof(w));
    memset(sum,0,sizeof(sum));
    cin>>n>>m;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
    }
    int f;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
        for(int i=1;i<=m;i++)
    {
         cin>>s[i]>>t[i];
         if(s[i]==t[i])
         {
             sum[s[i]]++;
         }
    }
    int k;
    for(int i=1;i<=n;i++)
    {
        if(w[i]==0)
        {
            cout<<sum[i]<<" ";
        }
        else
        {
            cout<<"0"<<" ";
        }
    }
    return 0;
}

by GuessYCB @ 2017-10-03 11:28:42

给你看我的25分（滑稽）。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define IL inline
#define RG register
#define maxn 300000
using namespace std;

inline int gi()
{
    int date = 0,m = 1; char ch = 0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar();
    if(ch == '-'){m = -1 ; ch = getchar();}
    while('0'<=ch && ch<='9'){
        date = date * 10 + ch - '0';
        ch = getchar();
    }return date * m;
}
inline void write(int ac)
{
    if(ac>9)write(ac/10);
    putchar(ac%10+'0');
}

vector<int>sur[maxn];
struct Road{int to,next;}t[2*maxn+5];  int head[maxn];
int W[maxn],tp[maxn];
struct Player
{
    int S,T;
    IL void Read(){S = gi(); T = gi();}
}p[maxn];
struct SegMent_Tree{int date,laz;}s[maxn];
int fa[maxn],siz[maxn],dep[maxn],son[maxn],top[maxn],cod[maxn];
int N,M,Ans,SUM,cnt;

void Dfs(int maste,int u,int fa,int Dist)
{
    if(!Dist){sur[maste].push_back(u);return;}
    for(int i = head[u];i;i = t[i].next)
    {
        int v = t[i].to;
        if(v == fa)continue;
        Dfs(maste,v,u,Dist-1);
    }return;
}

void Dfs1(int u,int fth,int deep)
{
    fa[u] = fth;
    siz[u] = 0; dep[u] = deep; son[u] = 0;
    for(int i = head[u];i;i = t[i].next)
    {
        int v = t[i].to;
        if(v == fth)continue;
        Dfs1(v,u,deep+1);
        siz[u] = siz[u] + siz[v];
        if(!son[u]||siz[son[u]]<siz[v])son[u] = v;
    }return;
}

void Dfs2(int u,int upp)
{
    top[u] = upp; cod[u] = ++SUM;
    if(son[u])Dfs2(son[u],upp);
    else return;
    for(int i = head[u];i;i = t[i].next)
    {
        int v = t[i].to;
        if(v == fa[u])continue;
        Dfs2(v,v);
    }return;
}

void PushDown(int rt,int l,int r)
{
    int mid = (l+r)>>1;
    s[rt<<1].laz = s[rt<<1|1].laz = s[rt].laz;
    s[rt<<1].date = (mid-l+1)*s[rt].laz + s[rt<<1].date;
    s[rt<<1|1].date = (r-mid)*s[rt].laz + s[rt<<1|1].date;
    s[rt].laz = 0; return;
}

void Modify(int ro,int l,int r,int tl,int tr,int chg)
{
    if(l>tr || r<tl)return;
    if(tl <= l && r <= tr)
    {
        s[ro].date = s[ro].date + chg*(r-l+1);
        s[ro].laz = s[ro].laz + chg;
        return;
    }
    if(s[ro].laz)PushDown(ro,l,r);
    int mid = (l+r)>>1;
    Modify(ro<<1,l,mid,tl,tr,chg);
    Modify(ro<<1|1,mid+1,r,tl,tr,chg);
    s[ro].date = s[ro<<1].date + s[ro<<1|1].date;
}

int Query(int ro,int l,int r,int tpos)
{
    if(l == r && tpos == l)return s[ro].date;
    PushDown(ro,l,r);
    int mid = (l+r)>>1;
    if(tpos<=mid)return Query(ro<<1,l,mid,tpos);
    else return Query(ro<<1|1,mid+1,r,tpos);
}

void Low_Bound(int nw)
{
    for(int i = 0 ; i < sur[nw].size(); i ++)
    {
        int gg = sur[nw][i];
        int L = 1,R = M,Res = 0;
        while(L<=R)
        {
            int Mid = (L+R)>>1;
            if(p[Mid].S>=gg){R = Mid-1; Res = Mid;}
            else L = Mid+1;
        }
        if(p[Res].S != sur[nw][i])continue;
        if(Res<=0 || Res>M)continue;
        for(int j = Res; j <= M ; j ++)
        {
            if(p[j].S==p[Res].S)tp[++cnt] = j;
            else break;
        }
    }
}

bool Check(int targ,int x1,int x2)
{
    int f1 = top[x1],f2 = top[x2]; bool flag = 0;
    while(f1 != f2)
    {
        if(dep[f1]<dep[f2]){swap(x1,x2);swap(f1,f2);}
        Modify(1,1,SUM,cod[x1],cod[f1],1);
        if(Query(1,1,SUM,cod[targ])!=0)flag = 1;
        Modify(1,1,SUM,cod[x1],cod[f1],-1);
        if(flag)return true;
        x1 = fa[f1]; f1 = top[x1];
    }
    if(dep[x1]>dep[x2])swap(x1,x2);
    Modify(1,1,SUM,cod[x1],cod[x2],1);
    if(Query(1,1,SUM,cod[targ])!=0)flag = 1;
    Modify(1,1,SUM,cod[x1],cod[x2],-1);
    if(flag)return true;
    return false;           //不在路径上
}

bool cmp1(int A,int B){return A<B;}
bool cmp2(Player A,Player B){return A.S<B.S;}

int main()
{
    freopen("Run.in","r",stdin);
    N = gi(); M = gi();
    for(int i = 1; i <= N-1 ; i ++)
    {
        int u = gi(),v = gi();
        t[++cnt] = (Road){v,head[u]};  head[u] = cnt;
        t[++cnt] = (Road){u,head[v]};  head[v] = cnt;
    }
    for(int i = 1; i <= N ; i ++)W[i] = gi();
    for(int i = 1; i <= N ; i ++)
    {
        while(!sur[i].empty())sur[i].pop_back();
        Dfs(i,i,0,W[i]);
        sort(sur[i].begin(),sur[i].end(),cmp1);
    }
    for(int i = 1; i <= M ; i ++)p[i].Read();
    sort(p+1,p+M+1,cmp2);
    SUM = 0;
    Dfs1(1,0,1); Dfs2(1,1);
    for(int i = 1; i <= N ; i ++)
    {
        cnt = 0; Ans = 0;
        Low_Bound(i);
        for(int j = 1; j <= cnt ; j ++)
          if(Check(i,p[tp[j]].S,p[tp[j]].T))Ans++;
        write(Ans); putchar(' ');
    }
    return 0;
}