oj.uz

Submission #574728

# Submission time Handle Problem Language Result Execution time Memory
574728 2022-06-09T10:41:21 Z FatihSolak Ideal city (IOI12_city) C++17
55 / 100
 215 ms 15148 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9;
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 % mod;
}

Compilation message

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

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 388 KB Output is correct
2 Correct 44 ms 340 KB Output is correct
3 Correct 119 ms 440 KB Output is correct
4 Correct 97 ms 340 KB Output is correct
5 Correct 207 ms 488 KB Output is correct
6 Correct 152 ms 524 KB Output is correct
7 Correct 215 ms 588 KB Output is correct
8 Correct 157 ms 468 KB Output is correct
9 Correct 144 ms 468 KB Output is correct
10 Correct 141 ms 468 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3188 KB Output is correct
2 Correct 14 ms 3328 KB Output is correct
3 Correct 35 ms 7584 KB Output is correct
4 Correct 37 ms 7464 KB Output is correct
5 Correct 103 ms 15148 KB Output is correct
6 Correct 85 ms 14920 KB Output is correct
7 Correct 79 ms 14920 KB Output is correct
8 Correct 80 ms 14984 KB Output is correct
9 Correct 82 ms 14656 KB Output is correct
10 Correct 86 ms 15108 KB Output is correct

Subtask #4
0 / 45.0

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