QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#540901#8133. When Anton Saw This Task He Reacted With 😩PhantomThreshold#TL 0ms3616kbC++204.2kb2024-08-31 18:05:072024-08-31 18:05:10

Judging History

你现在查看的是最新测评结果

  • [2024-08-31 18:05:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3616kb
  • [2024-08-31 18:05:07]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
using namespace std;
const int MOD=998244353;

signed main()
{
	ios_base::sync_with_stdio(false);
	const int B=300,maxd=17;
	struct vc
	{
		int x,y,z;
		vc operator+(const vc &k)const{return (vc){(x+k.x)%MOD,(y+k.y)%MOD,(z+k.z)%MOD};}
		vc operator-(const vc &k)const{return (vc){(x-k.x)%MOD,(y-k.y)%MOD,(z-k.z)%MOD};}
		vc operator*(const int k)const{return (vc){(x*k)%MOD,(y*k)%MOD,(z*k)%MOD};}
		vc operator*(const vc &k)const{return (vc){(y*k.z-z*k.y)%MOD,(z*k.x-x*k.z)%MOD,(x*k.y-y*k.x)%MOD};}
		vc operator^(const vc &k)const{return (vc){(x*k.x)%MOD,(y*k.y)%MOD,(z*k.z)%MOD};}
	};
	int n,q;
	
	cin>>n>>q;
	vector<vc> a(n+5);
	vector<int> L(n+5),R(n+5),pa(n+5);
	vector<vector<int>> jmp(maxd+5,vector<int>(n+5));
	for(int i=1;i<=n;i++)
	{
		string ty;
		cin>>ty;
		if(ty=="x")
		{
			cin>>L[i]>>R[i];
			pa[L[i]]=i;pa[R[i]]=i;
		}
		else
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
		}
	}
	vector<pair<int,vc>> mods(q+5);
	for(int i=1;i<=q;i++)
	{
		int pos;
		vc d;
		cin>>pos>>d.x>>d.y>>d.z;
		mods[i]=make_pair(pos,d);
	}
	vector<int> dfn(n+5),dfne(n+5),dep(n+5);
	int idx=0;
	function<void(int)> dfs0=[&](int x)
	{
		dfn[x]=++idx;
		if(L[x])
		{
			jmp[0][L[x]]=jmp[0][R[x]]=x;
			dep[L[x]]=dep[R[x]]=dep[x]+1;
			dfs0(L[x]);
			dfs0(R[x]);
		}
		dfne[x]=idx;
	};
	dep[1]=1;
	dfs0(1);
	for(int d=1;d<=maxd;d++)
	{
		for(int i=1;i<=n;i++)
			jmp[d][i]=jmp[d-1][jmp[d-1][i]];
	}
	
	auto lca=[&](int x,int y)
	{
		if(dep[x]>dep[y])swap(x,y);
		for(int d=maxd;d>=0;d--)
		{
			if(dep[y]-(1<<d)>=dep[x])
				y=jmp[d][y];
		}
		if(x==y)return x;
		for(int d=maxd;d>=0;d--)
		{
			if(jmp[d][x]!=jmp[d][y])
				x=jmp[d][x],y=jmp[d][y];
		}
		return jmp[0][x];
	};
	auto kthp=[&](int x,int k)
	{
		for(int d=maxd;d>=0;d--)
		{
			if((k>>d)&1)
				x=jmp[d][x];
		}
		return x;
	};
	const vc X=(vc){1,0,0},Y=(vc){0,1,0},Z=(vc){0,0,1};
	for(int l=1;l<=q;l+=B)
	{
		vector<int> gop(n+5),gopm(n+5),sp(n+5),csp(n+5);
		vector<vc> cfx(n+5),cfy(n+5),cfz(n+5);
		int r=min(q,l+B-1);
		vector<int> tmp,tmp2;
		tmp2.push_back(1);
		for(int i=l;i<=r;i++)
		{
			tmp2.push_back(mods[i].first);
		}
		sort(tmp2.begin(),tmp2.end(),[&](int x,int y){return dfn[x]<dfn[y];});
		tmp=tmp2;
		for(int i=0;i+1<(int)tmp2.size();i++)
		{
			tmp.push_back(lca(tmp2[i],tmp2[i+1]));
		}
		sort(tmp.begin(),tmp.end(),[&](int x,int y){return dfn[x]<dfn[y];});
		tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
		stack<int> s;
		for(auto z:tmp)
		{
			sp[z]=1;
			if(s.empty())s.push(z);
			else
			{
				int pp=s.top();
				while(not(dfn[pp]<=dfn[z] and dfne[z]<=dfne[pp]))
				{
					s.pop();
					pp=s.top();
				}
				gop[z]=pp;
				gopm[z]=kthp(z,dep[z]-dep[gop[z]]-1);
				s.push(z);
			}
		}
		function<void(int)> dfs1=[&](int u)
		{
			if(sp[pa[u]])
			{
				cfx[u]=X;
				cfy[u]=Y;
				cfz[u]=Z;
			}
			csp[u]=sp[u];
			if(L[u])
			{
				dfs1(L[u]);
				dfs1(R[u]);
				if(csp[L[u]] or csp[R[u]])
					csp[u]=1;
			}
			if(not sp[u])
			{
				if(csp[L[u]])
				{
					cfx[L[u]]=(X*a[R[u]])^cfx[u];
					cfy[L[u]]=(Y*a[R[u]])^cfy[u];
					cfz[L[u]]=(Z*a[R[u]])^cfz[u];
				}
				else
				{
					cfx[R[u]]=(a[L[u]]*X)^cfx[u];
					cfy[R[u]]=(a[L[u]]*Y)^cfy[u];
					cfz[R[u]]=(a[L[u]]*Z)^cfz[u];
				}
			}
			if(L[u])a[u]=a[L[u]]*a[R[u]];
		};
		dfs1(1);
		/*
		cerr<<"---\n";
		for(int j=1;j<=n;j++)
			cerr<<a[j].x<<' '<<a[j].y<<' '<<a[j].z<<endl;
		cerr<<"---\n";
		
		for(auto z:tmp)cerr<<z<<' ';
		cerr<<endl;
		*/
		reverse(tmp.begin(),tmp.end());
		for(int i=l;i<=r;i++)
		{
			a[mods[i].first]=mods[i].second;
			for(auto z:tmp)
			{
				if(L[z])
				{
					a[z]=a[L[z]]*a[R[z]];
				}
				vc tmp3;
				tmp3=tmp3+cfx[z]*a[z].x;
				tmp3=tmp3+cfy[z]*a[z].y;
				tmp3=tmp3+cfz[z]*a[z].z;
				if(gopm[z]!=z)a[gopm[z]]=tmp3;
			}
			
			cout<<a[1].x<<' '<<a[1].y<<' '<<a[1].z<<"\n";
			/*
			cerr<<"---\n";
			for(int j=1;j<=n;j++)
				cerr<<a[j].x<<' '<<a[j].y<<' '<<a[j].z<<endl;
			cerr<<"---\n";
			*/
		}
	}
	
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

5 3
x 2 3
v 1 0 1
x 4 5
v 0 2 1
v 1 1 1
4 1 2 3
5 0 1 1
4 0 2 2

output:

-2 0 2
1 -2 -1
0 0 0

result:

ok 9 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

199999 100000
x 137025 65661
v 572518668 158967010 74946561
x 129836 192657
x 141948 187810
v 574918069 328924434 141474729
x 143312 111002
x 52772 148497
v 922857701 690080961 651915759
v 656198340 28002884 129579416
v 639893144 265359784 646791226
v 796871409 411409966 598676495
v 882562617 224394...

output:

0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
...

result: