QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#517110 | #1197. Draw in Straight Lines | yqh2025 | ML | 0ms | 0kb | C++14 | 3.5kb | 2024-08-13 08:09:03 | 2024-08-13 08:09:03 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,k,Q,m;
int X[N],Y[N],Z[N];
int lm[N];
vector<int>E[N],G[N],H[N];
priority_queue<pair<int,int> >sl[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >sr[N];
struct ed{
int u,v,w;
}edge[N<<2];
int vis[N],deg[N];
map<pair<int,int>,int>mp;
bool cmp(ed x,ed y){
return x.w>y.w;
}
int fa[N<<1];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);}
int tot,a[N<<1];
int father[N<<1][22],dep[N<<1];
int getans(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[father[x][i]]>=dep[y])x=father[x][i];
if(x==y)return a[x];
for(int i=20;i>=0;i--)if(father[x][i]!=father[y][i])x=father[x][i],y=father[y][i];
return a[father[x][0]];
}
void sol(){
for(int i=1;i<=n;i++)X[i]=Y[i]=Z[i]=vis[i]=deg[i]=0;
mp.clear();
for(int i=1;i<=n;i++){
E[i].clear(),G[i].clear(),H[i].clear();
while(!sl[i].empty())sl[i].pop();
while(!sr[i].empty())sr[i].pop();
}
for(int i=1;i<=tot;i++){
dep[i]=0;a[i]=0;
for(int j=0;j<=20;j++)father[i][j]=0;
}
for(int i=1;i<=m;i++)edge[i].u=edge[i].v=edge[i].w=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld",&X[i],&Y[i]),Z[i]=0;
scanf("%lld",&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%lld%lld%lld",&x,&y,&lm[i]),deg[x]++,deg[y]++;
edge[i].u=x,edge[i].v=y;
mp[{x,y}]=mp[{y,x}]=i;
H[x].push_back(y);H[y].push_back(x);
lm[i]=sqrtl(lm[i]*lm[i]-(X[x]-X[y])*(X[x]-X[y])-(Y[x]-Y[y])*(Y[x]-Y[y]));
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
for(int i=1;i<=n;i++)q.push({deg[i],i});
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i:H[u]){
if(vis[i])continue;
E[u].push_back(i);
G[i].push_back(u);
deg[i]--;
q.push({deg[i],i});
}
}
for(int i=1;i<=n;i++){
for(int j:E[i]){
sl[i].push({-lm[mp[{i,j}]],j}),sr[i].push({lm[mp[{i,j}]],j});
}
}
scanf("%lld",&k);
for(int i=1;i<=k;i++){
int u,h;scanf("%lld%lld",&u,&h);
Z[u]+=h;
while(!sl[u].empty()&&sl[u].top().first>Z[u]){
int j=sl[u].top().second,s=sl[u].top().first;sl[u].pop();
if(s!=Z[j]-lm[mp[{u,j}]])continue;
if(!edge[mp[{u,j}]].w)edge[mp[{u,j}]].w=i;
}
while(!sr[u].empty()&&sr[u].top().first<Z[u]){
int j=sr[u].top().second,s=sr[u].top().first;sr[u].pop();
if(s!=Z[j]+lm[mp[{u,j}]])continue;
if(!edge[mp[{u,j}]].w)edge[mp[{u,j}]].w=i;
}
for(int v:G[u]){
if(edge[mp[{u,v}]].w!=0)continue;
int l=Z[u]-lm[mp[{u,v}]],r=Z[u]+lm[mp[{u,v}]];
if(Z[v]<l||Z[v]>r){
edge[mp[{u,v}]].w=i;
}
else sl[v].push({Z[u]-lm[mp[{u,v}]],u}),sr[v].push({Z[u]+lm[mp[{u,v}]],u});
}
}
for(int i=1;i<=n;i++)E[i].clear();
for(int i=1;i<=m;i++)if(edge[i].w==0)edge[i].w=k+1;
sort(edge+1,edge+m,cmp);
for(int i=1;i<=n+n-1;i++)fa[i]=i;
tot=n;
for(int i=1;i<=m;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(find(u)!=find(v)){
tot++;a[tot]=w;
u=find(u),v=find(v);
fa[u]=fa[v]=tot;
father[u][0]=father[v][0]=tot;
}
}
if(tot!=n+n-1)cout<<"A";
for(int i=tot;i;i--){
dep[i]=dep[father[i][0]]+1;
for(int j=1;j<=20;j++){
father[i][j]=father[father[i][j-1]][j-1];
}
}
scanf("%lld",&Q);
for(int i=1;i<=Q;i++){
int x,y;scanf("%lld%lld",&x,&y);
int ans=getans(x,y);
if(ans>k)ans=-1;
printf("%lld\n",ans);
// printf("-1\n");
}
exit(0);
}
signed main(){
int t;cin>>t;
while(t--)sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
3 3 1 2 3 .#. ### .#.