Submission #1176966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176966		sleepntsheep	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	149 ms	14516 KiB

kyoto

#include<stdio.h>
#include<string.h>
#include<queue>

#define N 211111

struct A{
    int i;long long c[2];
    bool operator<(const A&o)const{
	return c[0]*1ll*o.c[1]<c[1]*1ll*o.c[0];
    }
}a[N];

int h,w,ds[N],p[N];
long long ans,rc[N],dc[N];

int fnd(int i){
    return ds[i]<0?i:(ds[i]=fnd(ds[i]));
}
void unte(int i,int j){
    if((i=fnd(i))==(j=fnd(j)))return;
    ds[j]=i;
    ans+=a[i].c[1]*1ll*a[j].c[0];
    a[i].c[0]+=a[j].c[0],a[i].c[1]+=a[j].c[1];
}

std::priority_queue<A>pq;
int main(){
    memset(ds,-1,sizeof ds);
    scanf("%d%d",&h,&w);
    for(int l,x,i=1;i<=h;++i){
	scanf("%d",&x);
	a[i].c[1]=x;
	if(i>1){
	    a[i].c[1]-=l;
	    p[i]=i-1;
	    a[i].c[0]=1;
	}else p[i]=0;
	dc[i]=a[i].c[1];
	l=x;
	a[i].i=i;
    }

    for(int l,x,i=1;i<=w;++i){
	scanf("%d",&x);
	a[h+i].c[1]=x;
	if(i>1){
	    a[h+i].c[1]-=l;
	    p[h+i]=h+i-1;
	    a[h+i].c[0]=1;
	}else p[h+i]=0;
	rc[i]=a[h+i].c[1];
	l=x;
	a[h+i].i=h+i;
    }

    unte(1,h+1);
    for(int i=1;i<=h+w;++i)pq.push(a[i]);
    while(pq.size()){
	auto x=pq.top();pq.pop();
	int i=x.i;
	if(fnd(i)!=i)continue;
	if(i){
	    unte(p[i],i);
	    pq.push(a[fnd(p[i])]);
	}
    }

    for(int i=2;i<=h;++i){
	ans-=dc[i-1];
	dc[i]+=dc[i-1];
    }
    for(int i=2;i<=w;++i){
	ans-=rc[i-1];
	rc[i]+=rc[i-1];
    }

    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d%d",&h,&w);
      |     ~~~~~^~~~~~~~~~~~~~
kyoto.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
kyoto.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60