QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#467693#3029. The Great Drone ShowRong7AC ✓5262ms625372kbC++146.7kb2024-07-08 17:09:262024-07-08 17:09:26

Judging History

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

  • [2024-07-08 17:09:26]
  • 评测
  • 测评结果:AC
  • 用时:5262ms
  • 内存:625372kb
  • [2024-07-08 17:09:26]
  • 提交

answer

// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

#define inline __inline__ __attribute__ ((always_inline))

#define int long long

namespace io {
	int pos;
	inline int read (int &p = pos){
		static int v; static char c;
		v = 1, c = getchar (), p = 0;
		while (! isdigit (c)){
			if (c == '-')
				v = - 1;
			c = getchar ();
		}
		while (isdigit (c)){
			p = (p << 1) + (p << 3) + (c - 48);
			c = getchar ();
		}
		return p *= v;
	}
	inline void write (int x){
		if (x < 0)
			putchar ('-'), x = - x;
		static int sta[65], top;
		top = 0;
		do {
			sta[++ top] = x % 10;
			x /= 10;
		} while (x);
		while (top)
			putchar (sta[top --] + 48);
	}
};

const int N = 5e5, M = N * 3;

int n, m, t, q;
int x[N + 5], y[N + 5], z[N + 5], lim[M + 5];
struct edge {
	int u, v, l, tg;
} eg[M + 5];
vector < int > to[N + 5];
vector < pair < int , int > > fw[N + 5];
int deg[N + 5];

inline int RD (int x, int y, int z){
	return x * x + y * y + z * z;
}

set < pair < int , int > > sl[N + 5], sr[N + 5];
int ie[M + 5], fa[N + 5];

int find (int v){
	if (fa[v] == v)
		return fa[v];
	return fa[v] = find (fa[v]);
}

int firs[N + 5], nex[N * 2 + 5], eto[N * 2 + 5], w[N * 2 + 5], tot;
int dep[N + 5], gf[N + 5][20], gg[N + 5][20];
inline void Add (int u, int v, int l){
	++ tot;
	nex[tot] = firs[u];
	firs[u] = tot;
	eto[tot] = v;
	w[tot] = l;
}

void init (int u, int father, int wt = t + 1){
	dep[u] = dep[father] + 1;
	gf[u][0] = father;
	gg[u][0] = wt;
	for (int i = 1;i < 20;++ i){
		gf[u][i] = gf[gf[u][i - 1]][i - 1];
		gg[u][i] = min (gg[u][i - 1], gg[gf[u][i - 1]][i - 1]);
	}
	for (int e = firs[u], v;e;e = nex[e]){
		v = eto[e];
		if (v == father)
			continue;
//		printf (">%lld %lld %lld\n", u, v, w[e]);
		init (v, u, w[e]);
	}
}

inline int LCA (int u, int v){
	if (dep[u] < dep[v])
		swap (u, v);
	for (int i = 19;i >= 0;-- i)
		if (dep[gf[u][i]] >= dep[v])
			u = gf[u][i];
	if (u == v)
		return u;
	for (int i = 19;i >= 0;-- i)
		if (gf[u][i] != gf[v][i]){
			u = gf[u][i];
			v = gf[v][i];
		}
	return gf[u][0];
}

int T;
//int TT;

inline void ARKNIGHTS (){
//	int xx = 157, yy = 713;
//	if (xx > yy)
//		swap (xx, yy);
	
	
	io::read (n);
	for (int i = 1;i <= n;++ i)
		io::read (x[i]), io::read (y[i]), z[i] = 0, deg[i] = 0, to[i].clear (), fw[i].clear (), deg[i] = 0, sl[i].clear (), sr[i].clear ();
	io::read (m);
	
//	int idx = 0;
	
	for (int i = 1;i <= m;++ i){
		io::read (eg[i].u), io::read (eg[i].v), io::read (eg[i].l), eg[i].tg = N + 1;
		to[eg[i].u].push_back (i), to[eg[i].v].push_back (i);
		++ deg[eg[i].u], ++ deg[eg[i].v];
		if (RD (x[eg[i].u] - x[eg[i].v], y[eg[i].u] - y[eg[i].v], 0) > RD (0, 0, eg[i].l))
			lim[i] = - 1, eg[i].tg = 0;
		else {
			lim[i] = (int) floor (sqrt (RD (0, 0, eg[i].l) - RD (x[eg[i].u] - x[eg[i].v], y[eg[i].u] - y[eg[i].v], 0)));
			while (RD (x[eg[i].u] - x[eg[i].v], y[eg[i].u] - y[eg[i].v], lim[i]) > RD (0, 0, eg[i].l))
				-- lim[i];
		}
//		if (T == 355 && min (eg[i].u, eg[i].v) == xx && max (eg[i].u, eg[i].v) == yy)
//			printf ("%lld %lld, %lld %lld, %lld, %lld\n", x[eg[i].u], y[eg[i].u], x[eg[i].v], y[eg[i].v], eg[i].l, lim[i]), idx = i;
		ie[i] = i;
	}
	queue < int > Q;
	for (int i = 1;i <= n;++ i)
		if (deg[i] <= 6)
			Q.push (i);
//	if (T == 355)
//		printf ("%lld\n", idx);
	while (! Q.empty ()){
		int u = Q.front (), v;
		Q.pop ();
		deg[u] = 0;
		for (int e : to[u]){
			v = eg[e].u;
			if (eg[e].u == u)
				v = eg[e].v;
			if (deg[v] > 0){
				fw[u].push_back (make_pair (v, e));
//				if (T == 355 && u == xx)
//					printf ("(%lld %lld)\n", u, v);
				-- deg[v];
				if (deg[v] == 6)
					Q.push (v);
			}
		}
	}
	for (int i = 1, j, r;i <= n;++ i){
		for (auto e : fw[i]){
			tie (j, r) = e;
			sl[j].insert (make_pair (- lim[r], r));
			sr[j].insert (make_pair (lim[r], r));
		}
	}
	io::read (t);
//	int Tg = T;
	for (int T = 1, u, v, i, h, nl, nr;T <= t;++ T){
		io::read (u), io::read (h);
		for (auto e : fw[u]){
			tie (v, i) = e;
			nl = z[u] - lim[i];
			nr = z[u] + lim[i];
			if (sl[v].find (make_pair (nl, i)) != sl[v].end ()){
				sl[v].erase (make_pair (nl, i));
				sr[v].erase (make_pair (nr, i));
				if (z[v] < nl + h || z[v] > nr + h)
					eg[i].tg = T;
				else
					sl[v].insert (make_pair (nl + h, i)),
					sr[v].insert (make_pair (nr + h, i));
			}
		}
		z[u] += h;
//		if (T == 855 && Tg == 355)
//			printf ("%lld %lld\n", u, z[u]);
//		if (abs (z[xx] - z[yy]) > lim[idx] && Tg == 355)
//			printf (">> %lld %lld(%lld %lld)\n", z[xx], z[yy], u, h);
		pair < int , int > it;
		while (! sl[u].empty () && (it = *(-- sl[u].end ())).first > z[u]){
			eg[it.second].tg = T;
			sr[u].erase (make_pair (it.first + 2ll * lim[it.second], it.second));
			sl[u].erase (it);
		}
		while (! sr[u].empty () && (it = *(sr[u].begin ())).first < z[u]){
			eg[it.second].tg = T;
			sl[u].erase (make_pair (it.first - 2ll * lim[it.second], it.second));
			sr[u].erase (it);
		}
	}
	sort (ie + 1, ie + m + 1, [] (const int &i, const int &j){
		return eg[i].tg > eg[j].tg;
	});
	tot = 0;
	for (int i = 1;i <= n;++ i)
		firs[i] = 0, fa[i] = i, dep[i] = 0;
	for (int i = 1, e, u, v;i <= m;++ i){
		e = ie[i];
		u = eg[e].u, v = eg[e].v;
		if (find (u) != find (v)){
			Add (u, v, eg[e].tg);
			Add (v, u, eg[e].tg);
			fa[fa[u]] = fa[v];
		}
	}
	for (int i = 1;i <= n;++ i)
		if (dep[i] == 0)
			init (i, 0);
	io::read (q);
	while (q --){
//		++ TT;
		int u = io::read (), v = io::read (), lca = LCA (u, v);
//		if (TT != 8843)
//			continue;
//		printf ("<%lld>", lca);
		if (! lca)
			io::write (0), putchar ('\n');
		else {
			int res = t + 1;
//			int U = u, V = v;
			for (int i = 19;i >= 0;-- i){
				if (dep[gf[u][i]] >= dep[lca]){
					res = min (res, gg[u][i]);
					u = gf[u][i];
				}
				if (dep[gf[v][i]] >= dep[lca]){
					res = min (res, gg[v][i]);
					v = gf[v][i];
				}
			}
//			printf (">>>%lld %lld %lld %lld\n", U, V, lca, T);
//			while (U != lca){
//				printf ("<%lld %lld %lld>", U, gf[U][0], gg[U][0]);
//				U = gf[U][0];
//			}
//			puts ("");
//			while (V != lca){
//				printf ("<%lld %lld %lld>", V, gf[V][0], gg[V][0]);
//				V = gf[V][0];
//			}
			io::write (res > t ? - 1 : res), putchar ('\n');
		}
	}
}

signed main (){
//	bool tag = false;
	for (T = io::read ();T --;){
//		if (! tag){
//			io::read (x);
//			while (x --)
//				io::read (y), io::read (y);
//			io::read (x);
//			while (x --)
//				io::read (y), io::read (y), io::read (y);
//			io::read (x);
//			while (x --)
//				io::read (y), io::read (y);
//			io::read (x);
//			while (x --)
//				io::read (y), io::read (y);
//			tag = true;
//		} else
		ARKNIGHTS ();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 187ms
memory: 105496kb

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: 4618ms
memory: 524600kb

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: 4417ms
memory: 625372kb

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: 5262ms
memory: 518948kb

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