oj.uz

Submission #681980

# Submission time Handle Problem Language Result Execution time Memory
681980 2023-01-15T04:31:53 Z Qingyu Prize (CEOI22_prize) C++17
0 / 100
 2 ms 688 KB 
// test https://qoj.ac/submission/72284
#include<iostream>
#include<algorithm>
using namespace std;
const int o=1e6+10;
int n,K,q,T;
struct Edge{int v,p,w;};
struct Tree{
	int rt,fa[o],h[o],cnt,H[o],Cnt,tp[o],seq[o],dfn[o],s[o],hs[o],d[o],dep[o];bool vis[o];Edge e[o],E[o*4];
	inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
	inline void Ad(int U,int V,int W){E[++Cnt].v=V;E[Cnt].p=H[U];E[H[U]=Cnt].w=W;}
	inline void add(int U,int V,int W){Ad(U,V,W);Ad(V,U,-W);}
	void Dfs(int nw){
		s[nw]=1;
		for(int i=h[nw];i;i=e[i].p)
			d[e[i].v]=d[nw]+1,Dfs(e[i].v),s[nw]+=s[e[i].v],hs[nw]=(s[hs[nw]]>s[e[i].v]?hs[nw]:e[i].v);
	}
	void dfs(int nw,int ld){
		tp[nw]=ld;seq[dfn[nw]=++cnt]=nw;
		if(hs[nw]) dfs(hs[nw],ld);
		for(int i=h[nw];i;i=e[i].p) if(e[i].v^hs[nw]) dfs(e[i].v,e[i].v);
	}
	inline void init(){
		for(int i=1;i<=n;++i){
			cin>>fa[i];
			if(fa[i]>0) ad(fa[i],i);
			else rt=i;
		}
		Dfs(rt);cnt=0;dfs(rt,rt);
	}
	inline int lca(int x,int y){
		for(;tp[x]^tp[y];x=fa[tp[x]]) if(d[tp[x]]<d[tp[y]]) swap(x,y);
		return (d[x]<d[y])?x:y;
	}
	void ddfs(int nw){vis[nw]=1;for(int i=H[nw];i;i=E[i].p) if(!vis[E[i].v]) dep[E[i].v]=dep[nw]+E[i].w,ddfs(E[i].v);}
	inline int dis(int x,int y){return dep[x]+dep[y]-dep[lca(x,y)]*2;}
}T1,T2;
inline bool cmp(int A,int B){return T2.dfn[A]<T2.dfn[B];}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>K>>q>>T;//T1.init();T2.init();
	
	for(int i=1;i<=K;++i) T1.seq[i]=i;
	
	for(int i=1;i<=K;++i) cout<<T1.seq[i]<<" ";
	cout<<endl;
//	sort(T1.seq+1,T1.seq+K+1,cmp);
	for(int i=1;i<K;++i) cout<<"? "<<T1.seq[i]<<" "<<T1.seq[i+1]<<"\n";
	cout<<"!"<<endl;
	
	for(;T--;) cout<<"0 0\n";
	cout<<endl;
	return 0;
	
	for(int i=1,x,y,l1,l2,w;i<K;++i)
		x=T1.seq[i],y=T1.seq[i+1],l1=T1.lca(x,y),l2=T2.lca(x,y),
		cin>>w,T1.add(l1,x,w),cin>>w,T1.add(l1,y,w),cin>>w,T2.add(l2,x,w),cin>>w,T2.add(l2,y,w);
	T1.ddfs(T1.seq[1]);T2.ddfs(T1.seq[1]);
	for(int x,y;T--;cout<<T1.dis(x,y)<<" "<<T2.dis(x,y)<<"\n") cin>>x>>y;
	cout<<endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 552 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 680 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 300 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 300 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 688 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -