关于我开了O2全TLE,关了O2AC这档事
查看原帖
关于我开了O2全TLE,关了O2AC这档事
203102
Diamiko楼主2021/11/4 18:52

为啥啊???

以后noip都开O2,我因为这个爆零怎么办?

#include<bits/stdc++.h>
#define swap(a,b) a^=b^=a^=b
using namespace std;
const int N=1e5+5;
struct Node
{
	int l,r;
	mutable int v;
	Node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
	bool operator <(const Node &x)const
	{
		return l<x.l;
	}
};
set<Node>s;
int n,cnt=1,u,v,w;
int a[N],dep[N],val[N],id[N],top[N],head[N],siz[N],fa[N],son[N],nxt[N<<1],to[N<<1],len[N<<1];
inline void addEdge(int u,int v,int w)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	len[cnt]=w;
	head[u]=cnt;
}
inline int read()
{
	int x(0);char c(0);
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x;
}
void write(int x)
{
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
void dfs1(int u,int father)
{
	fa[u]=father;
	siz[u]=1;
	dep[u]=dep[father]+1;
	for(int e=head[u];e;e=nxt[e])
	{
		int v=to[e];
		if(!dep[v]&&v!=father)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			a[v]=len[e];
			if(siz[v]>siz[son[u]]) son[u]=v;
		}
	}
}
int tot;
void dfs2(int u,int t)
{
	top[u]=t;
	id[u]=++tot;
	val[tot]=a[u];
	s.insert(Node(tot,tot,a[u]));
	if(!son[u])return;
	dfs2(son[u],t);
	for(int e=head[u];e;e=nxt[e])
	{
		int v=to[e];
		if(v!=fa[u]&&v!=son[u])
		{
			dfs2(v,v);
		}
	}
}
inline auto split(int pos)
{
	auto it=s.lower_bound(Node(pos));
	if(it!=s.end()&&it->l==pos)return it;
	it--;
	int l=it->l,r=it->r,v=it->v;
	s.insert(Node(l,pos-1,v));
	return s.insert(Node(pos,r,v)).first;
}
inline void assign(int l,int r,int v)
{
	auto itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(Node(l,r,v));
}
char opt[10];
inline void cover(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		assign(id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	assign(id[x]+1,id[y],k);
}
inline void Plus(int l,int r,int k)
{
	for(auto itr=split(r+1),itl=split(l);itl!=itr;itl++)
	{
		itl->v+=k;
	}
}
inline void add(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		Plus(id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	Plus(id[x]+1,id[y],k);	
}
inline int MMMMMax(int l,int r)
{
	int maxx=-1;
	for(auto itr=split(r+1),itl=split(l);itl!=itr;itl++)
	{
		maxx=max(maxx,itl->v);
	}	
	return maxx;
}
inline int Max(int x,int y)
{
	int ans=-1;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,MMMMMax(id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=max(ans,MMMMMax(id[x]+1,id[y]));	
}
inline void change(int x,int k)
{
	int u=to[x*2],v=to[x*2^1];
	int son=fa[u]==v?u:v;
	auto it1=split(id[son]);
	auto it2=split(id[son]+1);
	it1->v=k;
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		u=read();v=read();w=read();
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	while(~scanf("%s",opt))
	{
		if(!strcmp(opt,"Stop"))break;
		if(!strcmp(opt,"Max"))
		{
			u=read(),v=read();
			write(Max(u,v));
			putchar('\n');
		}
		else if(!strcmp(opt,"Cover"))
		{
			u=read(),v=read(),w=read();
			cover(u,v,w);
		}
		else if(!strcmp(opt,"Add"))
		{
			u=read(),v=read(),w=read();
			add(u,v,w);
		}
		else
		{
			u=read(),v=read();
			change(u,v);
		}
	}
	return 0;
}
2021/11/4 18:52
加载中...