QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#517110#1197. Draw in Straight Linesyqh2025ML 0ms0kbC++143.5kb2024-08-13 08:09:032024-08-13 08:09:03

Judging History

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

  • [2024-08-13 08:09:03]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-08-13 08:09:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,k,Q,m;
int X[N],Y[N],Z[N];
int lm[N];
vector<int>E[N],G[N],H[N];
priority_queue<pair<int,int> >sl[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >sr[N];
struct ed{
	int u,v,w;
}edge[N<<2];
int vis[N],deg[N];
map<pair<int,int>,int>mp;
bool cmp(ed x,ed y){
	return x.w>y.w;
}
int fa[N<<1];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);}
int tot,a[N<<1];
int father[N<<1][22],dep[N<<1];
int getans(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)if(dep[father[x][i]]>=dep[y])x=father[x][i];
	if(x==y)return a[x];
	for(int i=20;i>=0;i--)if(father[x][i]!=father[y][i])x=father[x][i],y=father[y][i];
	return a[father[x][0]];
}
void sol(){
	for(int i=1;i<=n;i++)X[i]=Y[i]=Z[i]=vis[i]=deg[i]=0;
	mp.clear();
	for(int i=1;i<=n;i++){
		E[i].clear(),G[i].clear(),H[i].clear();
		while(!sl[i].empty())sl[i].pop();
		while(!sr[i].empty())sr[i].pop();
	}
	for(int i=1;i<=tot;i++){
		dep[i]=0;a[i]=0;
		for(int j=0;j<=20;j++)father[i][j]=0;
	}
	for(int i=1;i<=m;i++)edge[i].u=edge[i].v=edge[i].w=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&X[i],&Y[i]),Z[i]=0;
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%lld%lld%lld",&x,&y,&lm[i]),deg[x]++,deg[y]++;
		edge[i].u=x,edge[i].v=y;
		mp[{x,y}]=mp[{y,x}]=i;
		H[x].push_back(y);H[y].push_back(x);
		lm[i]=sqrtl(lm[i]*lm[i]-(X[x]-X[y])*(X[x]-X[y])-(Y[x]-Y[y])*(Y[x]-Y[y]));
	}
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	for(int i=1;i<=n;i++)q.push({deg[i],i});
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i:H[u]){
			if(vis[i])continue;
			E[u].push_back(i);
			G[i].push_back(u);
			deg[i]--;
			q.push({deg[i],i});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j:E[i]){
			sl[i].push({-lm[mp[{i,j}]],j}),sr[i].push({lm[mp[{i,j}]],j});
		}
	}
	scanf("%lld",&k);
	for(int i=1;i<=k;i++){
		int u,h;scanf("%lld%lld",&u,&h);
		Z[u]+=h;
		while(!sl[u].empty()&&sl[u].top().first>Z[u]){
			int j=sl[u].top().second,s=sl[u].top().first;sl[u].pop();
			if(s!=Z[j]-lm[mp[{u,j}]])continue;
			if(!edge[mp[{u,j}]].w)edge[mp[{u,j}]].w=i;
		}
		while(!sr[u].empty()&&sr[u].top().first<Z[u]){
			int j=sr[u].top().second,s=sr[u].top().first;sr[u].pop();
			if(s!=Z[j]+lm[mp[{u,j}]])continue;
			if(!edge[mp[{u,j}]].w)edge[mp[{u,j}]].w=i;
		}
		for(int v:G[u]){
			if(edge[mp[{u,v}]].w!=0)continue;
			int l=Z[u]-lm[mp[{u,v}]],r=Z[u]+lm[mp[{u,v}]];
			if(Z[v]<l||Z[v]>r){
				edge[mp[{u,v}]].w=i;
			}
			else sl[v].push({Z[u]-lm[mp[{u,v}]],u}),sr[v].push({Z[u]+lm[mp[{u,v}]],u});
		}
	}
	for(int i=1;i<=n;i++)E[i].clear();
	for(int i=1;i<=m;i++)if(edge[i].w==0)edge[i].w=k+1;
	sort(edge+1,edge+m,cmp);
	for(int i=1;i<=n+n-1;i++)fa[i]=i;
	tot=n;
	for(int i=1;i<=m;i++){
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		if(find(u)!=find(v)){
			tot++;a[tot]=w;
			u=find(u),v=find(v);
			fa[u]=fa[v]=tot;
			father[u][0]=father[v][0]=tot;
		}
	}
	if(tot!=n+n-1)cout<<"A";
	for(int i=tot;i;i--){
		dep[i]=dep[father[i][0]]+1;
		for(int j=1;j<=20;j++){
			father[i][j]=father[father[i][j-1]][j-1];
		}
	}
	scanf("%lld",&Q);
	for(int i=1;i<=Q;i++){
		int x,y;scanf("%lld%lld",&x,&y);
		int ans=getans(x,y);
		if(ans>k)ans=-1;
		printf("%lld\n",ans);
//		printf("-1\n");
	}
	exit(0);
}
signed main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

3 3 1 2 3
.#.
###
.#.

output:


result: