Submission #574726

#	Time	Username	Problem	Language	Result	Execution time	Memory
574726		FatihSolak	Ideal city (IOI12_city)	C++17	32 / 100	208 ms	3156 KiB

city

#include <bits/stdc++.h>
using namespace std;

int DistanceSum(int n, int *x, int *y) {
    vector<int> compressx,compressy;
    for(int i = 0;i<n;i++){
        compressx.push_back(x[i]);
        compressy.push_back(y[i]);
    }
    sort(compressx.begin(),compressx.end());
    sort(compressy.begin(),compressy.end());
    compressx.resize(unique(compressx.begin(),compressx.end())-compressx.begin());
    compressy.resize(unique(compressy.begin(),compressy.end())-compressy.begin());
    map<pair<int,int>,int> mp;
    for(int i = 0;i<n;i++){
        x[i] = lower_bound(compressx.begin(),compressx.end(),x[i]) - compressx.begin();
        y[i] = lower_bound(compressy.begin(),compressy.end(),y[i]) - compressy.begin();
        mp[{x[i],y[i]}] = 1;
    }
    long long ans = 0;
    if(n <= 5000){
        bool ok[compressx.size() + 1][compressy.size() + 1];
        int dist[compressx.size() + 1][compressy.size() + 1];
        for(int i = 0;i<=compressx.size();i++){
            for(int j = 0;j<=compressy.size();j++){
                ok[i][j] = dist[i][j] = 0;
            }
        }      
        for(int i = 0;i<n;i++){
            //cout << x[i] << " " <<  y[i] << endl;
            ok[x[i]][y[i]] = 1;
        }
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                dist[x[j]][y[j]] = -1;
            }
            queue<pair<int,int>> q;
            q.push({x[i],y[i]});
            dist[x[i]][y[i]] = 0;
            while(q.size()){
                auto tp = q.front();
                q.pop();
                int xx = tp.first;
                int yy = tp.second;
                ans += dist[xx][yy];
                for(int dx = -1;dx <=1;dx++){
                    for(int dy = -1;dy<=1;dy++){
                        if(abs(dx) + abs(dy) != 1)continue;
                        if(xx+dx < 0 || yy+dy < 0)continue;
                        if(ok[xx+dx][yy+dy] && dist[xx+dx][yy+dy] == -1){
                            dist[xx+dx][yy+dy] = dist[xx][yy] + 1;
                            q.push({xx+dx,yy+dy});
                        }
                    }
                }
            }
        }
        return ans/2;
    }
    vector<int> vx[n];
    vector<int> vy[n];
    for(int i = 0;i<n;i++){
        vx[x[i]].push_back(i);
        vy[y[i]].push_back(i);
    }
    long long sumx = 0,sumy = 0;
    long long cnt1 = 0,cnt2 = 0;
    for(int i = 0;i<n;i++){
        for(auto u:vx[i]){
            ans += cnt1 * i - sumx;
            cnt1++;
            sumx += i;
        }
        for(auto u:vy[i]){
            ans += cnt2 * i - sumy;
            cnt2++;
            sumy += i;
        }
    }
    return ans;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0;i<=compressx.size();i++){
      |                       ~^~~~~~~~~~~~~~~~~~
city.cpp:25:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             for(int j = 0;j<=compressy.size();j++){
      |                           ~^~~~~~~~~~~~~~~~~~
city.cpp:26:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |                 ok[i][j] = dist[i][j] = 0;
      |                            ~~~~~~~~~~~^~~
city.cpp:69:18: warning: unused variable 'u' [-Wunused-variable]
   69 |         for(auto u:vx[i]){
      |                  ^
city.cpp:74:18: warning: unused variable 'u' [-Wunused-variable]
   74 |         for(auto u:vy[i]){
      |                  ^

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