QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77455 | #3029. The Great Drone Show | ExplodingKonjac | AC ✓ | 7873ms | 492896kb | C++17 | 7.9kb | 2023-02-14 18:53:34 | 2023-02-14 18:53:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<22;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
};
class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x,target);
#endif
}
template<typename T>
inline void __write(T x)
{
static char stk[64],*top;top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target=f; }
#endif
template<typename ...T>
inline void writesp(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
inline void writeln(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
inline FastOutput &operator <<(char x)
{ return __putc(x),*this; }
inline FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
inline FastOutput &operator <<(const string &s)
{ return (*this)<<s.c_str(); }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator <<(const T &x)
{ return __write(x),*this; }
}qout;
class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc()
{
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f=stdin): FastIOBase(f){}
inline void setTarget(FILE *f) { target=f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x)
{ initializer_list<int>{(this->operator>>(x),0)...}; }
inline FastInput &operator >>(char &x)
{ while(isspace(x=__getc()));return *this; }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator >>(T &x)
{
static char ch,sym;x=sym=0;
while(isspace(ch=__getc()));
if(ch=='-') sym=1,ch=__getc();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
return sym?x=-x:x,*this;
}
inline FastInput &operator >>(char *s)
{
while(isspace(*s=__getc()));
for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
return *s='\0',*this;
}
inline FastInput &operator >>(string &s)
{
char str_buf[(1<<8)+1],*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=__getc()));
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
*p='\0',s.append(str_buf);
if(p!=buf_end) break;
}
return *this;
}
}qin;
} // namespace FastIO
using namespace FastIO;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
constexpr int INF=2e9;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif
int T,n,m,q,px[500005],py[500005],ph[500005];
int eu[2000005],ev[2000005],ew[2000005],brk[2000005];
struct Interval
{
int l,r,id;
Interval()=default;
Interval(int _l,int _r,int _i): l(_l),r(_r),id(_i){}
struct CmpL
{
inline bool operator ()(const Interval &x,const Interval &y)const
{
if(x.l!=y.l) return x.l>y.l;
else if(x.r!=y.r) return x.r<y.r;
else return x.id<y.id;
}
};
struct CmpR
{
inline bool operator ()(const Interval &x,const Interval &y)const
{
if(x.r!=y.r) return x.r<y.r;
else if(x.l!=y.l) return x.l<y.l;
else return x.id<y.id;
}
};
};
inline Interval calc(int u,int v,int id)
{
Interval res(INF,-INF,id);
LL x=px[v]-px[u],y=py[v]-py[u];
LL tmp=(LL)ew[id]*ew[id]-x*x-y*y;
if(tmp<0) return res;
tmp=sqrtl(tmp),res.l=ph[u]-tmp,res.r=ph[u]+tmp;
return res;
}
vector<pair<int,int>> gg[500005],gi[500005],go[500005];
int deg[500005];
struct NodeInfo
{
set<Interval,Interval::CmpL> sl;
set<Interval,Interval::CmpR> sr;
}a[500005];
inline void add(int u,const Interval &x)
{ a[u].sl.insert(x),a[u].sr.insert(x); }
inline void del(int u,const Interval &x)
{ a[u].sl.erase(x),a[u].sr.erase(x); }
void prework()
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
for(int i=1;i<=n;i++) gi[i].clear(),go[i].clear();
for(int i=1;i<=n;i++) q.emplace(deg[i],i);
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(deg[u]==-1) continue;
deg[u]=-1;
for(auto &[v,w]: gg[u])
{
if(deg[v]==-1) continue;
gi[v].emplace_back(u,w);
go[u].emplace_back(v,w);
q.emplace(--deg[v],v);
}
}
for(int u=1;u<=n;u++) for(auto &[v,w]: go[u])
{
auto lim=calc(v,u,w);
if(lim.l>lim.r) brk[w]=0;
else add(v,lim);
}
}
int fa[500005];
inline int findFa(int x)
{ return x!=fa[x]?fa[x]=findFa(fa[x]):x; }
inline void merge(int x,int y)
{ fa[findFa(y)]=findFa(x); }
int ord[2000005],dep[500005],f[500005][20],g[500005][20];
void dfs(int u,int faw=INF,int fa=0)
{
dep[u]=dep[fa]+1,f[u][0]=fa,g[u][0]=faw;
for(int i=1;(1<<i)<=dep[u];i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=1;(1<<i)<=dep[u];i++)
g[u][i]=min(g[u][i-1],g[f[u][i-1]][i-1]);
for(auto &[v,w]: gg[u])
if(v!=fa) dfs(v,w,u);
}
inline int query(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int res=INF;
for(int i=19;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
res=min(res,g[x][i]),x=f[x][i];
if(x==y) return res;
for(int i=19;i>=0;i--)
if(f[x][i]!=f[y][i])
res=min({res,g[x][i],g[y][i]}),x=f[x][i],y=f[y][i];
return min({res,g[x][0],g[y][0]});
}
void clearData()
{
for(int i=1;i<=n;i++)
{
gg[i].clear(),gi[i].clear(),go[i].clear();
a[i].sl.clear(),a[i].sr.clear();
dep[i]=deg[i]=px[i]=py[i]=ph[i]=0;
for(int j=0;j<20;j++) f[i][j]=g[i][j]=0;
}
}
int main()
{
qin>>T;
while(T--)
{
qin>>n;
for(int i=1;i<=n;i++) qin>>px[i]>>py[i],ph[i]=0;
qin>>m;
for(int i=1,u,v,w;i<=m;i++)
{
qin>>u>>v>>w,eu[i]=u,ev[i]=v,ew[i]=w;
brk[i]=INF,deg[u]++,deg[v]++;
gg[u].emplace_back(v,i);
gg[v].emplace_back(u,i);
}
prework();
qin>>q;
for(int i=1,u,x;i<=q;i++)
{
qin>>u>>x,ph[u]+=x;
for(auto &[v,w]: go[u])
{
if(brk[w]<INF) continue;
Interval tmp;
ph[u]-=x,tmp=calc(u,v,w),del(v,tmp);
ph[u]+=x,tmp=calc(u,v,w);
if(ph[v]<tmp.l || ph[v]>tmp.r) brk[w]=i;
else add(v,tmp);
}
auto it=a[u].sl.begin();
while(it!=a[u].sl.end() && it->l>ph[u])
{
if(brk[it->id]==INF) brk[it->id]=i;
a[u].sr.erase(*it);
a[u].sl.erase(it++);
}
it=a[u].sr.begin();
while(it!=a[u].sr.end() && it->r<ph[u])
{
if(brk[it->id]==INF) brk[it->id]=i;
a[u].sl.erase(*it);
a[u].sr.erase(it++);
}
}
for(int i=1;i<=n;i++) gg[i].clear();
iota(fa+1,fa+n+1,1),iota(ord+1,ord+m+1,1);
sort(ord+1,ord+m+1,[](int x,int y){ return brk[x]>brk[y]; });
for(int i=1;i<=m;i++)
{
int u=eu[ord[i]],v=ev[ord[i]];
if(findFa(u)==findFa(v)) continue;
int w=brk[ord[i]];
merge(u,v);
gg[u].emplace_back(v,w);
gg[v].emplace_back(u,w);
}
for(int i=1;i<=n;i++) if(!dep[i]) dfs(i);
qin>>q;
while(q--)
{
int u,v,res;
qin>>u>>v;
res=(findFa(u)==findFa(v)?query(u,v):0);
if(res==INF) res=-1;
qout.writeln(res);
}
clearData(); // multi tests, remember to clear.
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 251ms
memory: 110088kb
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: 7363ms
memory: 410104kb
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: 7261ms
memory: 492896kb
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: 7873ms
memory: 415196kb
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