QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#448516	#4401. Prize	Naganohara_Yoimiya	Compile Error	/	/	C++14	7.4kb	2024-06-19 18:18:14	2024-06-19 18:18:15

Judging History

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

[2024-06-19 18:18:15]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2024-06-19 18:18:14]
提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}

const int N=1e6+50;

int n,k,q;

struct zkw{
	int M,k,d[N<<2];
	void build(){
		M=1,k=0;while(M<n)M<<=1,k++;
		for(int i=1;i<=2*M-1;i++)d[i]=1e9;
	}
	void pushup(int p){d[p]=min(d[p<<1],d[p<<1|1]);}
	void ins(int p){
		d[p+M-1]=p,p+=M-1;
		for(int i=1;i<=k;i++)pushup(p>>i);
	}
	int qry(int l,int r){
		int res=1e9;
		for(l+=M-1,r+=M;l<r;l>>=1,r>>=1){
			if(l&1)cmin(res,d[l++]);
			if(r&1)cmin(res,d[--r]);
		}
		return res;
	}
};

struct BIT{
	int c[N];
	void clear(){memset(c,0,sizeof(c));}
	int lowbit(int x){return x&(-x);}
	void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
	int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
};

struct Tree{

vector<int>G[N];
int fa[N],hson[N],top[N],dfn[N],idfn[N],dep[N],sz[N],dfc,root;

void dfs1(int u){
	dep[u]=dep[fa[u]]+1,sz[u]=1;
	for(int v:G[u]){
		dfs1(v),sz[u]+=sz[v];
		if(sz[v]>sz[hson[u]])hson[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp,idfn[dfn[u]=++dfc]=u;
	if(hson[u])dfs2(hson[u],tp);
	for(int v:G[u])if(v!=hson[u])dfs2(v,v);
}

zkw T1,T3;
BIT T2;

int f[N];
void mdf(int x,int v){
	T2.add(dfn[x],v-f[x]),T2.add(dfn[x]+sz[x],f[x]-v);
	f[x]=v;
}
int qsum(int x){
	return T2.sum(dfn[x]);
}

int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	return u;
}
int qry(int x,int y){
	int z=LCA(x,y);
	int fx=qsum(x),fy=qsum(y),fz=qsum(z);
	return fx+fy-fz-fz;
}

int getpos_1(int x){
	int p=T1.qry(dfn[x],dfn[x]+sz[x]-1);
	if(p>n)return -1;
	return idfn[p];
}
int getpos_3(int x){
	int p=T3.qry(dfn[x],dfn[x]+sz[x]-1);
	if(p>n)return -1;
	return idfn[p];
}

bool In[N];
int mn1[N],mn2[N];

void build(vector<int>Fa){
	for(int i=1;i<=n;i++)fa[i]=Fa[i];
	for(int i=1;i<=n;i++){
		if(fa[i]!=-1)G[fa[i]].emplace_back(i);
		else root=i,fa[i]=0;
	}

	dfc=0,dep[root]=0;
	dfs1(root),dfs2(root,root);
	T1.build(),T2.clear(),T3.build();

	for(int i=1;i<=n;i++)In[i]=0,mn1[i]=mn2[i]=-1;
}

set<int>S1[N],S2[N];
void ins(int u,bool c){
	if(c){
		T3.ins(dfn[u]);
		if(mn2[top[u]]==-1||dep[mn2[top[u]]]>dep[u])mn2[top[u]]=u;
		S2[top[u]].insert(dep[u]);
	}
	T1.ins(dfn[u]);
	if(mn1[top[u]]==-1||dep[mn1[top[u]]]>dep[u])mn1[top[u]]=u;
	S1[top[u]].insert(dep[u]);
	In[u]=1;
}

void ins2(int u){ // --> real
	T3.ins(dfn[u]);
	if(mn2[top[u]]==-1||dep[mn2[top[u]]]>dep[u])mn2[top[u]]=u;
	S2[top[u]].insert(dep[u]);
}

int getf_1(int u){
	while(u){
		if(mn1[top[u]]!=-1&&dep[mn1[top[u]]]<=dep[u]){
			auto it=--S1[top[u]].upper_bound(dep[u]);
			int d=(*it);
			return idfn[dfn[top[u]]+d-dep[top[u]]];
		}
		u=fa[top[u]];
	}
	return -1;
}
int getf_2(int u){
	while(u){
		if(mn2[top[u]]!=-1&&dep[mn2[top[u]]]<=dep[u]){
			auto it=--S2[top[u]].upper_bound(dep[u]);
			int d=(*it);
			return idfn[dfn[top[u]]+d-dep[top[u]]];
		}
		u=fa[top[u]];
	}
	return -1;
}

void print(){
	for(int i=1;i<=n;i++)cout<<f[i]<<" ";puts("");
}

bool is_anc(int u,int v){return dfn[u]<=dfn[v]&&dfn[v]<=dfn[u]+sz[u]-1;}

}T1,T2;

Tree A1,A2;

auto QRY(int u,int v){
	int z1=A1.LCA(u,v),z2=A2.LCA(u,v);
	return make_tuple(A1.qry(u,z1),A1.qry(z1,v),A2.qry(u,z2),A2.qry(z2,v));
}

set<int>S;

struct Oper{
	int op;
	int u,v;
	int i,id,t;
};
vector<Oper>ops;

void Qry(int u,int v){
	Oper nw;
	nw.op=1,nw.u=u,nw.v=v;
	ops.emplace_back(nw);
}

ll tmp[8];
void Add(int i,int id){
	Oper nw;
	nw.op=2,nw.i=i,nw.id=id;
	ops.emplace_back(nw);
}
void Del(int i,int id){
	Oper nw;
	nw.op=3,nw.i=i,nw.id=id;
	ops.emplace_back(nw);
}
void Add2(int i,int t,int u,int v){
	Oper nw;
	nw.op=4,nw.i=i,nw.u=u,nw.v=v,nw.t=t;
	ops.emplace_back(nw);
}
void Del2(int i,int t,int u,int v){
	Oper nw;
	nw.op=5,nw.i=i,nw.u=u,nw.v=v,nw.t=t;
	ops.emplace_back(nw);
}
void Abs(int i){
	Oper nw;
	nw.op=8,nw.i=i;
	ops.emplace_back(nw);
}

void Mdf(int t,int u,int i){
	Oper nw;
	nw.op=6,nw.u=u,nw.i=i,nw.t=t;
	ops.emplace_back(nw);
}
void Clr(){
	Oper nw;
	nw.op=7;
	ops.emplace_back(nw);
}

int d[4];
void DO(Oper nw){
	if(nw.op==1){
		cin>>d[0]>>d[1]>>d[2]>>d[3];
		// auto [x,y,z,t]=QRY(nw.u,nw.v);
		// d[0]=x,d[1]=y,d[2]=z,d[3]=t;
	}
	if(nw.op==2)tmp[nw.i]+=d[nw.id];
	if(nw.op==3)tmp[nw.i]-=d[nw.id];
	if(nw.op==4)tmp[nw.i]+=(nw.t==1?T1.qry(nw.u,nw.v):T2.qry(nw.u,nw.v));
	if(nw.op==5)tmp[nw.i]-=(nw.t==1?T1.qry(nw.u,nw.v):T2.qry(nw.u,nw.v));
	if(nw.op==6){
		if(nw.t==1)T1.mdf(nw.u,tmp[nw.i]);
		if(nw.t==2)T2.mdf(nw.u,tmp[nw.i]);
	}
	if(nw.op==7)memset(tmp,0,sizeof(tmp));
	if(nw.op==8)tmp[nw.i]=abs(tmp[nw.i]);
}

void ins(int u){
	if(T2.In[u]){
		int v=T1.fa[u];
		cout<<"? "<<u<<" "<<v<<'\n';
		
		Qry(u,v);
		Add(1,0);
		Mdf(1,u,1);
		Clr();

		T2.ins2(u),T1.ins(u,0);
		return;
	}

	auto it=S.insert(T2.dfn[u]).first;int p=-1;
	if(it!=S.begin()){
		int z=T2.LCA(T2.idfn[*prev(it)],u);
		if(z!=u&&(!T2.In[z]))p=z;
	}
	if(++it!=S.end()){
		int z=T2.LCA(u,T2.idfn[*it]);
		if(z!=u&&(!T2.In[z]))p=z;
	}

	if(p!=-1){
		S.insert(T2.dfn[p]);

		int v=-1,vv=-1;
		for(int q:T2.G[p]){
			v=T2.getpos_3(q),vv=T2.getpos_1(q);
			if(v!=-1)break;
		}

		assert(v!=-1);

		cout<<"? "<<u<<" "<<v<<'\n';
		Qry(u,v);

		// int w1=a+b-T1.qry(T1.fa[u],v);
		// T1.mdf(u,w1);
		Add(1,0),Add(1,1),Del2(1,1,T1.fa[u],v),Mdf(1,u,1);

		int r=T2.getf_1(p);
		// int w3=d-T2.qry(v,vv);
		Add(3,3),Del2(3,2,v,vv);
		if(r!=-1){
			Add2(2,2,r,v),Del(2,3);
			// int w2=T2.qry(r,v)-d;
			// T2.mdf(p,w2);
			Mdf(2,p,2);
		}
		Add(4,2),Mdf(2,u,4);
		Mdf(2,vv,3);
		// T2.mdf(u,c);
		// T2.mdf(vv,w3);

		T1.ins(u,1),T2.ins(u,1),T2.ins(p,0);
	}
	else{
		int r=T2.getf_1(u),s=-1,ss=-1;
		for(int q:T2.G[u]){
			s=T2.getpos_1(q);
			if(s!=-1)break;
		}
		int v=T1.root;
		
		cout<<"? "<<u<<" "<<v<<'\n';
		Qry(u,v);

		Add(1,0),Add(1,1),Del2(1,1,T1.fa[u],v),Mdf(1,u,1);

		// int w2=0,w3=0;
		// if(r!=-1)w2=abs(T2.qry(v,r)-c-d);
		// if(s!=-1)w3=abs(c+d-T2.qry(s,v));
		// if(r!=-1)T2.mdf(u,w2);
		// if(s!=-1)T2.mdf(s,w3);

		if(r!=-1)Add2(2,2,v,r),Del(2,2),Del(2,3),Abs(2);
		if(s!=-1)Add2(3,2,s,v),Del(3,2),Del(3,3),Abs(3);
		if(r!=-1)Mdf(2,u,2);
		if(s!=-1)Mdf(2,s,3);

		T1.ins(u,1),T2.ins(u,1);
	}
	Clr();
}

int qq;

signed main(void){

// #ifndef ONLINE_JUDGE
// 	freopen("in.txt","r",stdin);
// #endif

	cin>>n>>k>>qq>>q;
	vector<int>Fa(n+1);
	for(int i=1;i<=n;i++)cin>>Fa[i];T1.build(Fa);
	for(int i=1;i<=n;i++)cin>>Fa[i];T2.build(Fa);
	
	vector<int>nodes(n);
	for(int i=1;i<=n;i++)nodes[i-1]=i;
	sort(nodes.begin(),nodes.end(),[&](int x,int y){return T1.dep[x]<T1.dep[y];});

	for(int i=0;i<k;i++)cout<<nodes[i]<<" \n"[i==k-1];
	T1.ins(nodes[0],0),T2.ins(nodes[0],1),S.insert(T2.dfn[nodes[0]]);
	for(int i=1;i<k;i++)ins(nodes[i]);
	cout<<"!"<<endl;

	for(auto nw:ops)DO(nw);

	vector<pair<int,int> >Qs(q);
	for(int _=0;_<q;_++)cin>>Qs[i].fi>>Qs[i].se;
	for(int _=0;_<q;_++){
		auto [u,v]=Qs[_];
		cout<<T1.qry(u,v)<<" "<<T2.qry(u,v);
		if(_<q-1)cout<<'\n';
	}
	cout<<endl;

	return 0;
}

Source code, Language: C++14

Details

answer.code: In function ‘int main()’:
answer.code:369:37: error: ‘i’ was not declared in this scope
  369 |         for(int _=0;_<q;_++)cin>>Qs[i].fi>>Qs[i].se;
      |                                     ^
answer.code:371:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  371 |                 auto [u,v]=Qs[_];
      |                      ^