0分求调！
查看原帖
0分求调！
1267517
pengyilin楼主2024/5/19 13:52

这题太离谱了。而且是又难又离谱。

试了两次，都显示我编译信息错误。

求大佬指点！（本蒟蒻想要代码）。

TLE代码：

#include<bits/stdc++.h>
using namespace std;
const int mx = 3e5+10, LOG = 20, inf = 1e9;
int n, m, ans[mx], s[mx], t[mx], w[mx];
int head[mx], nxt[mx<<1], to[mx<<1], tot;
int dep[mx] = {-1}, fa[mx][LOG];
int down[mx<<2], up[mx<<1];
vector<pair<int, int> > v[mx];
void add(int u, int v)
{
	++tot;
	nxt[tot] = head[u];
	to[tot] = v;
	head[u] = tot;
}
void dfs0(int u)
{
	for(int i = 1; i < LOG; ++i){
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	for(int e = head[u], v; e; e = nxt[e]){
		if((v=to[e]) == fa[u][0]) continue;
		fa[v][0] = u;
		dep[v] = dep[u]+1;
		dfs0(v);
	}
}
int lca(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = LOG-1; ~i; --i)
		if (dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if(u == v) return u;
	for(int i = LOG-1; ~i; --i)
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
#define pb push_back
#define mp make_pair
#define fi first
#define se second
void addr(int s, int t, int w=0)
{
	assert(dep[s] != dep[t]);
	if(dep[s] < dep[t]) w += inf, swap(s, t);
	v[s].pb(mp(w, 1));
	v[t].pb(mp(w, -1));
}
void dfs(int u)
{
	ans[u] -= up[dep[u]+w[u]] + down[(mx<<1) + dep[u]-w[u]];
	for(int e = head[u]; e; e = nxt[e]){
		if(to[e] == fa[u][0]) continue;
		dfs(to[e]);
	}
	for(int i = 0; i < (int)v[u].size(); ++i){
		if(v[u][i].fi > inf/2) down[(mx<<1) + v[u][i].fi-inf] += v[u][i].se;
		else up[v[u][i].fi] += v[u][i].se;
	}
	ans[u] += up[dep[u]+w[u]] + down[(mx<<1) + dep[u]-w[u]];
}
int main()
{
	scanf("%d%d", &n, &m);
	int u, v;
	for(int i = 0; i < n-1; ++i){
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dfs0(1);
	for(int i = 1; i <= n; ++i) scanf("%d", w+i);
	for(int i = 1; i <= m; ++i){
		scanf("%d%d", s+i, t+i);
		u = lca(s[i], t[i]);
		if(u == s[i]) addr(fa[s[i]][0], t[i], dep[s[i]]);
		else if (u == t[i]) addr(s[i], fa[t[i]][0], dep[s[i]]);
		else {
			addr(s[i], fa[u][0], dep[s[i]]);
			addr(u, t[i], dep[u] - (dep[s[i]]-dep[u]));
		}
	}
	dfs(1);
	for(int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i==n]);
	return 0;
}

RE代码：

#include<bits/stdc++.h>
#define N 300002
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
struct EDGE{
    int nextt,to;
}w[N*2];
struct play{
    int s,t,lca,len;
}p[N];
int tot=0; 
int head[N],f[N][21],dep[N],T[N],tong[N],tong2[N],num[N],ans[N];
vector<int>a[N],b[N],c[N];
void add(int a,int b)
{
    tot++;
    w[tot].nextt=head[a];
    w[tot].to=b;
    head[a]=tot;
}
void dfs(int x)
{
    for(int i=head[x];i;i=w[i].nextt)
    {
        int v=w[i].to;
        if(v==f[x][0])continue;
        dep[v]=dep[x]+1;
        f[v][0]=x;
        for(int i=1;i<=20;++i)f[v][i]=f[f[v][i-1]][i-1];
        dfs(v);
    }
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void dfs_up(int x)
{
    int now=dep[x]+T[x],last=tong[now];
    for(int i=head[x];i;i=w[i].nextt)
    {
        int v=w[i].to;
        if(v==f[x][0])continue;
        dfs_up(v);
    }
    tong[dep[x]]+=num[x];
    ans[x]+=tong[now]-last;
    for(int i=0;i<a[x].size();++i)tong[dep[a[x][i]]]--;
}
void dfs_down(int x)
{
    int now=dep[x]-T[x],last=tong2[now+N];
    for(int i=head[x];i;i=w[i].nextt)
    {
        int v=w[i].to;
        if(v==f[x][0])continue;
        dfs_down(v);
    }
    for(int i=0;i<b[x].size();++i)tong2[b[x][i]+N]++;
    ans[x]+=tong2[now+N]-last;
    for(int i=0;i<c[x].size();++i)tong2[c[x][i]+N]--;
} 
int main()
{
    int n=read(),m=read();
    for(int i=1;i<n;++i)
    {
        int a=read(),b=read();
        add(a,b);add(b,a);
    }
    dep[1]=1;
    dfs(1);
    for(int i=1;i<=n;++i)
      T[i]=read();
    for(int i=1;i<=m;++i)
    {
        p[i].s=read();p[i].t=read();
        num[p[i].s]++;
        p[i].lca=LCA(p[i].s,p[i].t);
        p[i].len=dep[p[i].s]+dep[p[i].t]-2*dep[p[i].lca];
        a[p[i].lca].push_back(p[i].s);
        b[p[i].t].push_back(dep[p[i].t]-p[i].len);
        c[p[i].lca].push_back(dep[p[i].t]-p[i].len);
    }
    dfs_up(1);
    dfs_down(1);
    for(int i=1;i<=m;++i)
      if(dep[p[i].s]-dep[p[i].lca]==T[p[i].lca])ans[p[i].lca]--;
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);
    return 0;
}

Compile Error代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int ans,tot,k;
int s[10];
int main()
{
	cin>>n;
	cin>>s[1]>>s[2]>>s[3]>>s[4]>>s[5]<<s[6];
	for(int i=1,x;i<=n;i++){
		cin>>x;
	    if(x==0){
		    tot=0;
	    }
	    else {
			tot++;
			if(tot<3) k=s[1];
			else if(tot<7) k=s[2];
			else if(tot<30) k=s[3];
			else if(tot<120) k=s[4];
			else if(tot<365) k=s[5];
			else k=s[6];
			ans+=k;
		}
	cout<<ans<<'\n';
	return 0;
}

求大佬指点。

2024/5/19 13:52