Submission #31107

#	Time	Username	Problem	Language	Result	Execution time	Memory
31107		h0ngjun7	Ideal city (IOI12_city)	C++14	32 / 100	186 ms	4056 KiB

city

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
struct data{
    ll num,x,y;
    bool operator ==(const data R)const{
        return x==R.x && y==R.y;
    }
    bool operator <(const data R)const{
        return x<R.x || (x==R.x && y<R.y);
    }
 
};
set<data > S;
queue<ll> Q;
ll X[100004],Y[100005],dis[2005],dy[4]={0,1,0,-1},dx[4]={1,0,-1,0};
vector<ll> cango[2005];
bool used[2005];
ll N,mod=1000000000;
int sub3(){
    ll sum=0,sum1=0;
 
//    for(ll i=1;i<=N;i++){
//        for(ll j=i+1;j<=N;j++){
//            sum1+=abs(X[i]-X[j])+abs(Y[i]-Y[j]);
//        }
//    }
//    printf("%lld\n",sum1);
    sort(X+1,X+1+N);sort(Y+1,Y+1+N);
    for(ll i=N,j=N-1;i>=1;i--,j-=2){
        sum+=(X[i]*j%mod)+(Y[i]*j%mod);
        sum%=mod;
    }
    return (int)sum;
 
}
int sub2(){
    ll ans=0;
    for(ll i=1;i<=N;i++) S.insert((data){i,X[i],Y[i]});
    for(ll i=1;i<=N;i++){
        for(ll j=0;j<4;j++){
            ll ty=Y[i]+dy[j];
            ll tx=X[i]+dx[j];
            auto it=S.find((data){2,tx,ty});
            if(it!=S.end()){
                cango[i].push_back((*it).num);
            }
        }
    }
 //   printf("%lld ",S.size());
 
    for(ll i=1;i<=N;i++){
        Q.push(i);
        memset(used,0,sizeof(used));
        memset(dis,0,sizeof(dis));
        used[i]=true;
      //  printf("i:%lld\n",i);
        while(!Q.empty()){
            ll from=Q.front();Q.pop();
            if(from>i) ans+=dis[from],ans%=mod;
            for(int i=0;i<cango[from].size();i++){
                if(!used[cango[from][i]]){
                    used[cango[from][i]]=true;
                    dis[cango[from][i]]=dis[from]+1;
                    Q.push(cango[from][i]);
                }
            }
        }
    }
    return ans%mod;
}
int DistanceSum(int iN, int *iX, int *iY) {
 
    N=iN;
    for(int i=1;i<=N;i++) X[i]=iX[i-1],Y[i]=iY[i-1];
    if(N<=2000) return sub2();
    return sub3();
 
 
  return N;
 
}

Compilation message (stderr)

city.cpp: In function 'int sub3()':
city.cpp:22:14: warning: unused variable 'sum1' [-Wunused-variable]
     ll sum=0,sum1=0;
              ^
city.cpp: In function 'int sub2()':
city.cpp:62:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<cango[from].size();i++){
                          ^

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45