QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#98899 | #3029. The Great Drone Show | chenxinyang2006 | AC ✓ | 8844ms | 470920kb | C++14 | 5.4kb | 2023-04-20 20:45:36 | 2023-04-20 20:45:38 |
Judging History
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