当前位置:网站首页>Bzoj3545: [ontak2010] peaks

Bzoj3545: [ontak2010] peaks

2020-12-07 15:04:46 osc_ twlari2q

Subject portal
.

solution :
Good question .
It's just not mandatory online .
Forcing online means it won't .


offline .
First x The points that can be reached can actually reach each other .
So we can think of it as a connecting block .
In fact, it is the minimum spanning tree to require the edge weight to be as small as possible .


Offline, first press the x Sort .
And then, in turn, build less than or equal to x The minimum spanning tree of .
Then the current v At the end of the link block k Big is actually the answer .
When searching and compressing paths, merge the chairman tree .


Make complaints :
The time limit is too small .40s Ok or not .
This machine is too slow. It runs at every point 5 second .
Submit TLE.
At this time, of course, it's time to find karchang to optimize .
It's amazing %%%.
Fast reading of metaphysics .
And a bunch of things I couldn't find in the code before ..
Get my five second program to three .
then 7000ms+ After that








Code implementation :

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
inline char nc() {
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(void) {
    char ch=nc();
    int sum=0;
    while(!(ch>='0'&&ch<='9'))
        ch=nc();
    while(ch>='0'&&ch<='9')
        sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();
    return sum;
}
struct node {
  
  int lc,rc,c;}t[2000001];int cnt,rt[200001];
inline void build(int &u,int l,int r,int p) {
    if(u==0)u=++cnt;t[u].c++;
    if(l==r)return ;int mid=(l+r)/2;
    if(p<=mid)build(t[u].lc,l,mid,p);
    else build(t[u].rc,mid+1,r,p);
}
int fa[100001];inline int findfa(int x) {
  
  if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];}
void Merge(int &u1,int u2) {
    if(u1==0) {u1=u2;return ;}if(u2==0)return ;
    t[u1].c+=t[u2].c;
    Merge(t[u1].lc,t[u2].lc);
    Merge(t[u1].rc,t[u2].rc);
}
int S[100001];
inline int find(int u,int l,int r,int k) {
    if(t[u].c<k)return -1;
    if(l==r)return S[l];
    int mid=(l+r)/2;
    if(k<=t[t[u].rc].c)return find(t[u].rc,mid+1,r,k);
    else return find(t[u].lc,l,mid,k-t[t[u].rc].c);
}
struct trnode {
  
  int x,y,c,id,ans;}a[500001],Q[500001];int len;
bool cmp(trnode n1,trnode n2) {
  
  return n1.c<n2.c;}
bool cmp2(trnode n1,trnode n2) {
  
  return n1.y<n2.y;}
struct edge {
  
  int x,id;}s[500001];
bool cmp1(edge n1,edge n2) {
  
  return n1.x<n2.x;}
bool cmp3(trnode n1,trnode n2) {
  
  return n1.id<n2.id;}
int main() {
    //freopen("3545.in","r",stdin);freopen("3545.out","w",stdout);
    int n,m;n=read(),len=read(),m=read();cnt=0;
    for(int i=1;i<=n;i++) {s[i].x=read();s[i].id=i;}
    sort(s+1,s+1+n,cmp1);int tot=0;
    for(int i=1;i<=n;i++) {
        if(s[i].x!=s[i-1].x)tot++;S[tot]=s[i].x;
        build(rt[s[i].id],1,n,tot);
    }
    for(register int i=1;i<=len;++i) {a[i].x=read();a[i].y=read();a[i].c=read();}
    for(register int i=1;i<=m;++i) {
        Q[i].x=read();Q[i].y=read();Q[i].c=read();Q[i].id=i;
    }
    for(int i=1;i<=n;++i)fa[i]=i;
    sort(a+1,a+len+1,cmp);sort(Q+1,Q+1+m,cmp2);int tt=1;
    for(register int i=1;i<=m;++i) {
        for(register int j=tt;j<=len;++j) {
            if(a[j].c>Q[i].y) {tt=j;break;}
            int xx=findfa(a[j].x),yy=findfa(a[j].y);
            if(xx!=yy) {fa[xx]=yy;Merge(rt[yy],rt[xx]);}
            if(j==len)tt=len+1;
        }Q[i].ans=find(rt[findfa(Q[i].x)],1,n,Q[i].c);
    }sort(Q+1,Q+1+m,cmp3);
    for(int i=1;i<=m;i++)printf("%d\n",Q[i].ans);
    return 0;
}

版权声明
本文为[osc_ twlari2q]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207150436872z.html