求问用scanf WA92分

P3038 [USACO11DEC] Grass Planting G

Cap1taL @ 2022-08-03 19:15:28

只WA了一个点

代码

// Problem: P3038 [USACO11DEC]Grass Planting G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3038
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define MAXM 100003
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define ford(a,b,c) for(int a=b;a>=c;a--)
#define RT return 0;
#define db(x)   cout<<endl<<x<<endl;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
    LXF x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){ 
    if(ch=='-') w=-1;
    ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
    x=x*10+(ch-'0');
    ch=getchar();
    }
    return x*w;
}
inline void out(LXF x){
    if(x<0){
    x=-x;
    putchar('-');
    }
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
int n,m,a[MAXN],id[MAXN],dep[MAXN],top[MAXN],fa[MAXN],siz[MAXN],son[MAXN],cnt,ecnt,head[MAXN];
struct E{
    int v,nxt;
}e[MAXM<<1];
void add_e(int u,int v){
    e[++ecnt]=(E){v,head[u]};
    head[u]=ecnt;
}
void dfs1(int s,int fath){
    fa[s]=fath;
    siz[s]=1;
    dep[s]=dep[fath]+1;
    int maxson=-1;
    for(int i=head[s];i;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fath){
            dfs1(v,s);
            siz[s]+=siz[v];
            if(siz[v]>maxson){
                maxson=siz[v];
                son[s]=v;
            }
        }
    }
}
void dfs2(int s,int topf){
    id[s]=++cnt;
    top[s]=topf;
    if(!son[s]) return ;
    dfs2(son[s],topf);
    for(int i=head[s];i;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa[s]&&v!=son[s]){
            dfs2(v,v);
        }
    }
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])   swap(x,y);
    return y;
}
//SegTree
struct Segtree{
    int l,r,sum,lz;
}tr[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return 1+(x<<1);}
void push_up(int p){
    tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
}
void update(int p,int k){
    tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
    tr[p].lz+=k;
}
void push_down(int p){
    update(lc(p),tr[p].lz);
    update(rc(p),tr[p].lz);
    tr[p].lz=0;
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r)    return ;
    int mid=(l+r)>>1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    push_up(p);
}
void modify(int p,int nl,int nr,int k){
    int l=tr[p].l,r=tr[p].r;
    if(r<nl||nr<l)  return ;
    if(nl<=l&&r<=nr){
        update(p,k);
        return ;
    }
    push_down(p);
    modify(lc(p),nl,nr,k);
    modify(rc(p),nl,nr,k);
    push_up(p);
}
int qurey(int p,int nl,int nr){
    int l=tr[p].l,r=tr[p].r;
    if(r<nl||nr<l)  return 0;
    if(nl<=l&&r<=nr)    return tr[p].sum;
    push_down(p);
    return qurey(lc(p),nl,nr)+qurey(rc(p),nl,nr);
}
void updRange(int x,int y,int k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        // printf("modify(1,%d,%d,%d)\n",id[top[x]],id[x],k);
        modify(1,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])   swap(x,y);
    // printf("modify(1,%d,%d,%d)\n",id[y],id[x],k);
    modify(1,id[y],id[x],k);
}
int main(){
    n=RIN,m=RIN;
    foru(i,1,n-1){
        int u=RIN,v=RIN;
        add_e(u,v);
        add_e(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char op;
        scanf("%c",&op);
        int x=RIN,y=RIN;
        if(op=='P'){
            updRange(x,y,1);
            int lca=LCA(x,y);
            updRange(lca,lca,-1);
        }else{
            printf("%d\n",qurey(1,id[(dep[x]>dep[y]?x:y)],id[(dep[x]>dep[y]?x:y)]));
        }
    }
    return 0;
}

RIN是快读,见上方define,a=RIN相当于a=read()

最后那个地方如果改成cin>>op>>x>>y就AC了

如果按代码里的写,那个测试点尽管只有一个Q,会输出很多次0

测试点如下:

in
7 7 
3 1 
3 2 
3 4 
3 5 
3 6 
3 7 
P 1 2 
P 4 2 
P 5 2 
P 6 2 
P 3 2 
P 7 2 
Q 3 2 

out
6

by yqyx @ 2022-08-03 19:39:01

scanf("%c",&op);

会读入回车。


by xieyikai2333 @ 2022-08-03 19:48:00

@XHZS_XY 切记,读入字符时要

scanf(" %c",&op);
       ^

这个空格千万不能少!!!


by Cap1taL @ 2022-08-03 21:18:13

@xieyikai2333 谢谢各位dalao


|