QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98899#3029. The Great Drone Showchenxinyang2006AC ✓8844ms470920kbC++145.4kb2023-04-20 20:45:362023-04-20 20:45:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-20 20:45:38]
  • 评测
  • 测评结果:AC
  • 用时:8844ms
  • 内存:470920kb
  • [2023-04-20 20:45:36]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define mem(a,b) memset(a,b,sizeof(a))
#define mpy(a,b) memcpy(a,b,sizeof(b))
#define dbg(...) cerr<<"#"<<__LINE__<<": "<<__VA_ARGS__<<endl
#define Fi(s) freopen(s,"r",stdin)
#define Fo(s) freopen(s,"w",stdout)
#define Fio(s) Fi(s".in"),Fo(s".out")
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}

/*template <class T,class U>
inline void add(T &x,U y){
	x += y;
	if(x >= mod) x -= mod;
}

template <class T,class U>
inline void sub(T &x,U y){
	x -= y;
	if(x < 0) x += mod;
}

ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n,m,K,q;
int px[500005],py[500005];
int _u[1500005],_v[1500005],res[1500005],ord[1500005];
ll rr[1500005],h[1500005];

bool cmp(int x,int y){
	return res[x] > res[y];
}

ll sqr(ll x){
	return x * x;
}

vector <pii> G[500005],anc[500005];//dist id
int vis[500005],deg[500005];
queue <int> Q;
set <pll> L[500005],R[500005];

int cnt;
int head[500005];
struct eg{
	int to,nxt,w;
}edge[1000005];

void make(int u,int v,int w){
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

namespace UNS{
	int fa[500005];
	void init(){
		rep(u,1,n) fa[u] = u;
	}
	int fnd(int x){
		if(fa[x] == x) return x;
		return fa[x] = fnd(fa[x]);
	}
}
int to[20][500005],Mn[20][500005],dep[500005];
void dfs(int u,int f){
	vis[u] = 1;
	to[0][u] = f;
	dep[u] = dep[f] + 1;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == f) continue;
		dfs(v,u);
		Mn[0][v] = edge[i].w;
	}
}

int qry(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	int ans = inf;
	per(k,18,0){
		if(dep[to[k][u]] >= dep[v]){
			chkmin(ans,Mn[k][u]);
			u = to[k][u];
		}
	}
	if(u == v) return ans;
	per(k,18,0){
		if(to[k][u] != to[k][v]){
			chkmin(ans,Mn[k][u]);
			chkmin(ans,Mn[k][v]);
			u = to[k][u];
			v = to[k][v];
		}
	}
	chkmin(ans,Mn[0][u]);
	chkmin(ans,Mn[0][v]);
	return ans;
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d%d",&px[i],&py[i]);
		G[i].clear();anc[i].clear();L[i].clear();R[i].clear();
	}
	fill(vis + 1,vis + n + 1,0);
	fill(deg + 1,deg + n + 1,0);
	fill(h + 1,h + n + 1,0);
	cnt = 0;
	fill(head + 1,head + n + 1,0);
	scanf("%d",&m);
	fill(res + 1,res + m + 1,inf);
	rep(i,1,m){
		int w;
		scanf("%d%d%d",&_u[i],&_v[i],&w);
		G[_u[i]].eb(mkp(i,_v[i]));G[_v[i]].eb(mkp(i,_u[i]));
		rr[i] = sqrtl(1ll * w * w - sqr(px[_u[i]] - px[_v[i]]) - sqr(py[_u[i]] - py[_v[i]]));
		deg[_u[i]]++;deg[_v[i]]++;
	}
	rep(u,1,n){
		if(deg[u] <= 5){
			deg[u] = -1;
			Q.push(u);
		}
	}
	while(!Q.empty()){
		int u = Q.front();
		vis[u] = 1;
		Q.pop();
		for(pii I:G[u]){
			if(vis[I.second]) continue;
			anc[u].eb(I);
			if(deg[I.second] < 0) continue;
			deg[I.second]--;
			if(deg[I.second] <= 5){
				deg[I.second] = -1;
				Q.push(I.second);
			}
		}
	}
	rep(u,1,n){
		for(pii I:anc[u]){
			L[I.second].insert(mkp(-rr[I.first],I.first));
			R[I.second].insert(mkp(rr[I.first],I.first));
		}
	}
	scanf("%d",&K);
	rep(i,1,K){
		int u,delta;
		scanf("%d%d",&u,&delta);
		h[u] += delta;
		auto it = L[u].upper_bound(mkp(h[u],inf));
		while(it != L[u].end()){
			chkmin(res[it->second],i);
			it = L[u].erase(it);
		}
		it = R[u].begin();
		while(it != R[u].end() && it->first < h[u]){
			chkmin(res[it->second],i);
			it = R[u].erase(it);
		}
		for(pii I:anc[u]){
			if(res[I.first] != inf) continue;

			if(abs(h[u] - h[I.second]) > rr[I.first]){
				res[I.first] = i;
				continue;
			}
			it = L[I.second].find(mkp(h[u] - delta - rr[I.first],I.first));
			assert(it != L[I.second].end());
			L[I.second].erase(it);
			L[I.second].insert(mkp(h[u] - rr[I.first],I.first));

			it = R[I.second].find(mkp(h[u] - delta + rr[I.first],I.first));
			assert(it != R[I.second].end());
			R[I.second].erase(it);
			R[I.second].insert(mkp(h[u] + rr[I.first],I.first));
		}
	}
//	rep(i,1,m) printf("%d ",res[i]);
//	printf("\n");
	rep(i,1,m) ord[i] = i;
	sort(ord + 1,ord + m + 1,cmp);
	UNS::init();
	rep(i,1,m){
		int pu = UNS::fnd(_u[ord[i]]),pv = UNS::fnd(_v[ord[i]]);
		if(pu == pv) continue;
		UNS::fa[pu] = pv;
		make(_u[ord[i]],_v[ord[i]],res[ord[i]]);
		make(_v[ord[i]],_u[ord[i]],res[ord[i]]);
	}
	fill(vis + 1,vis + n + 1,0);
	rep(u,1,n) if(!vis[u]) dfs(u,0);
	rep(i,1,18){
		rep(u,1,n){
			to[i][u] = to[i - 1][to[i - 1][u]];
			Mn[i][u] = min(Mn[i - 1][u],Mn[i - 1][to[i - 1][u]]);
		}
	}
	scanf("%d",&q);
	rep(i,1,q){
		int u,v;
		scanf("%d%d",&u,&v);
		int ret = qry(u,v);
		if(ret == inf) printf("-1\n");
		else printf("%d\n",ret);
	}
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 285ms
memory: 174908kb

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: 7931ms
memory: 395736kb

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: 7952ms
memory: 470920kb

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: 8844ms
memory: 394588kb

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