QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468303#3029. The Great Drone ShowyhdddAC ✓9682ms770356kbC++143.9kb2024-07-08 20:11:332024-07-08 20:11:35

Judging History

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

  • [2024-07-08 20:11:35]
  • 评测
  • 测评结果:AC
  • 用时:9682ms
  • 内存:770356kb
  • [2024-07-08 20:11:33]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=1500010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,m,k,p;
pii a[maxn];int h[maxn];
struct edge{
	int u,v,w;
}E[maxn];
namespace krus{
	int f[maxn],idx,tim[maxn];
	int fd(int x){
		if(f[x]==x)return x;
		return f[x]=fd(f[x]);
	}
	int to[21][maxn],dep[maxn];
	void kru(){
		sort(E+1,E+m+1,[&](edge u,edge v){
			return u.w>v.w;
		});
		for(int i=1;i<=2*n;i++)f[i]=i;idx=n;
		for(int i=1;i<=m;i++){
			int u=fd(E[i].u),v=fd(E[i].v);
			if(u==v)continue;
			else f[u]=f[v]=++idx,to[0][u]=to[0][v]=idx,tim[idx]=E[i].w,to[0][idx]=0;
		}
		for(int j=1;j<=20;j++){
			for(int i=1;i<=idx;i++)to[j][i]=to[j-1][to[j-1][i]];
		}
		for(int i=idx;i;i--)dep[i]=dep[to[0][i]]+1;
	}
	int lca(int u,int v){
		if(dep[u]<dep[v])swap(u,v);
		for(int i=20;~i;i--)if(dep[to[i][u]]>=dep[v])u=to[i][u];
		if(u==v)return u;
		for(int i=20;~i;i--)if(to[i][u]!=to[i][v])u=to[i][u],v=to[i][v];
		return to[0][u];
	}
	int que(int u,int v){
		int tp=lca(u,v);
		return tim[tp]==inf?-1:tim[tp];
	}
}
int head[maxn],tot;
struct nd{
	int nxt,to,w;
}e[maxn];
void add(int u,int v,int w){e[++tot]={head[u],v,w};head[u]=tot;}
vector<pii> g[maxn];
int d[maxn];set<pii> q;
set<pii> sl[maxn],sr[maxn];
bool chk(int u,int v,int l){
	return (h[u]-h[v])*(h[u]-h[v])+(a[u].fi-a[v].fi)*(a[u].fi-a[v].fi)+(a[u].se-a[v].se)*(a[u].se-a[v].se)<=l*l;
}
int get(int u,int v,int l){
	int len=l*l-(a[u].fi-a[v].fi)*(a[u].fi-a[v].fi)-(a[u].se-a[v].se)*(a[u].se-a[v].se);
	if(len<0)return -inf;
	int ss=sqrtl(len);
	while(ss*ss>len)ss--;
	while((ss+1)*(ss+1)<=len)ss++;
	return ss;
}
void work(){
	for(int i=1;i<=n;i++)head[i]=0;tot=0;
	for(int i=1;i<=n;i++)g[i].clear(),h[i]=d[i]=0,sl[i].clear(),sr[i].clear();
	n=read();
	for(int i=1;i<=n;i++)a[i]={read(),read()};
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),l=read();
		g[u].push_back({v,l}),g[v].push_back({u,l});
		d[u]++,d[v]++;
	}
	for(int i=1;i<=n;i++)q.insert({d[i],i});
	for(int i=1;i<=n;i++){
		int u=(*q.begin()).se;q.erase(q.begin());
		for(auto[v,w]:g[u])if(q.find({d[v],v})!=q.end()){
			add(u,v,w);
			int lim=get(u,v,w);
			// cout<<u<<" "<<v<<" "<<w<<" "<<lim<<"\n";
			if(lim==-inf)E[tot]={u,v,0};
			else E[tot]={u,v,inf},sl[v].insert({-lim,tot}),sr[v].insert({lim,tot});
			q.erase({d[v],v});d[v]--;q.insert({d[v],v});
		}
	}
	k=read();
	for(int t=1;t<=k;t++){
		int u=read(),l=read();
		h[u]+=l;
		while(sl[u].size()&&h[u]<(*--sl[u].end()).fi){
			if(E[(*--sl[u].end()).se].w>k)E[(*--sl[u].end()).se].w=t;
			sl[u].erase(--sl[u].end());
		}
		while(sr[u].size()&&h[u]>(*sr[u].begin()).fi){
			if(E[(*sr[u].begin()).se].w>k)E[(*sr[u].begin()).se].w=t;
			sr[u].erase(sr[u].begin());
		}
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;if(E[i].w<=k)continue;
			if(!chk(u,v,e[i].w)){
				E[i].w=t;
				int lim=get(u,v,e[i].w);
				sl[v].erase({-lim+h[u]-l,i}),sr[v].erase({lim+h[u]-l,i});
			}
			else{
				int lim=get(u,v,e[i].w);
				sl[v].erase({-lim+h[u]-l,i}),sl[v].insert({-lim+h[u],i});
				sr[v].erase({lim+h[u]-l,i}),sr[v].insert({lim+h[u],i});
			}
		}
	}
	// for(int i=1;i<=m;i++)cout<<E[i].u<<" "<<E[i].v<<" "<<E[i].w<<"\n";
	p=read();krus::kru();
	while(p--){
		int u=read(),v=read();
		printf("%lld\n",krus::que(u,v));
	}
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
	// cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=read();
	while(T--)work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 250ms
memory: 239024kb

input:

389
686
10357458 -45685083
-13525616 -46849548
13245371 -52959727
1533241 -47731445
29767995 -57009848
8709026 -49429890
-10596975 -37749761
-2292572 -57107130
-9505231 -38312854
-61987063 -5380598
31126084 -56985867
2632716 -48068309
17172532 -54294658
-9557851 -38286352
12761654 -53122994
16653770...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 139675 lines

Test #2:

score: 0
Accepted
time: 9295ms
memory: 669216kb

input:

2
500000
14564495 88542502
14369974 88737023
14295451 88811546
14576134 88530863
14275155 88831842
14376399 88730598
14495717 88611280
14627448 88479549
14409262 88697735
14197920 88909077
14514752 88592245
14230630 88876367
14593804 88513193
14254688 88852309
14446490 88660507
14601040 88505957
143...

output:

499999
499999
499999
362592
499999
499999
499999
499999
499999
499999
500000
499999
499999
499999
500000
499999
499999
500000
500000
500000
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
499999
500000...

result:

ok 1000000 lines

Test #3:

score: 0
Accepted
time: 9074ms
memory: 770356kb

input:

2
500000
-19378149 -1495147
-63216117 1581244
-19385210 -1493025
-19413444 -1485172
-19378687 -1494837
-19385262 -1493222
-19416893 -1484193
-19382610 -1493888
-19394475 -1490854
-19389700 -1492007
-19368978 -1497516
-19411475 -1485807
-19409427 -1486310
-19410593 -1486127
-19398571 -1489556
-194185...

output:

-1
-1
-1
-1
-1
-1
287736
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
438438
-1
-1
-1
426237
434139
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
343746
-1
-1
-1
228939
-1
-1
263585
-1
-1
-1
-1
-1
-1
491977
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
108087
-1
-1
-1
...

result:

ok 700000 lines

Test #4:

score: 0
Accepted
time: 9682ms
memory: 678000kb

input:

2
500000
-14328778 23720400
-14328778 23760511
-14328778 23608513
-14328778 23472063
-14328778 23478531
-14328778 23831736
-14328778 23498966
-14328778 23429182
-14328778 23466244
-14328778 23663462
-14328778 23798751
-14328778 23731882
-14328778 23476840
-14328778 23514441
-14328778 23747035
-14328...

output:

451240
397300
-1
331036
363448
166109
-1
352060
-1
424519
-1
-1
-1
250539
-1
152767
-1
474347
300896
306646
185236
417574
493445
-1
442324
414082
379274
414954
-1
178698
120502
-1
120599
396406
-1
325710
350531
304703
485967
498734
165205
406031
-1
397300
335709
-1
323677
386421
399220
393304
23021
...

result:

ok 1000000 lines