QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77455#3029. The Great Drone ShowExplodingKonjacAC ✓7873ms492896kbC++177.9kb2023-02-14 18:53:342023-02-14 18:53:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-14 18:53:39]
  • 评测
  • 测评结果:AC
  • 用时:7873ms
  • 内存:492896kb
  • [2023-02-14 18:53:34]
  • 提交

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