oj.uz

Submission #31107

# Submission time Handle Problem Language Result Execution time Memory
31107 2017-08-10T01:38:23 Z h0ngjun7 Ideal city (IOI12_city) C++14
32 / 100
 186 ms 4056 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3792 KB Output is correct
2 Correct 0 ms 3792 KB Output is correct
3 Correct 0 ms 3792 KB Output is correct
4 Correct 0 ms 3792 KB Output is correct
5 Correct 0 ms 3792 KB Output is correct
6 Correct 0 ms 3792 KB Output is correct
7 Correct 0 ms 3792 KB Output is correct
8 Correct 0 ms 3792 KB Output is correct
9 Correct 0 ms 3792 KB Output is correct
10 Correct 3 ms 3792 KB Output is correct
11 Correct 0 ms 3792 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3924 KB Output is correct
2 Correct 36 ms 3924 KB Output is correct
3 Correct 89 ms 3924 KB Output is correct
4 Correct 89 ms 3924 KB Output is correct
5 Correct 173 ms 4056 KB Output is correct
6 Correct 149 ms 4056 KB Output is correct
7 Correct 186 ms 4056 KB Output is correct
8 Correct 153 ms 4056 KB Output is correct
9 Correct 143 ms 4056 KB Output is correct
10 Correct 119 ms 4056 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3936 KB Output isn't correct
2 Halted 0 ms 0 KB -