oj.uz

Submission #574724

# Submission time Handle Problem Language Result Execution time Memory
574724 2022-06-09T10:28:57 Z FatihSolak Ideal city (IOI12_city) C++17
32 / 100
 206 ms 1952 KB 
#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 <= 2000){
        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;
    }
    return ans/2;
}

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;
      |                            ~~~~~~~~~~~^~~

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 0 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 3 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 4 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 53 ms 340 KB Output is correct
2 Correct 43 ms 340 KB Output is correct
3 Correct 113 ms 440 KB Output is correct
4 Correct 98 ms 452 KB Output is correct
5 Correct 201 ms 588 KB Output is correct
6 Correct 145 ms 540 KB Output is correct
7 Correct 206 ms 536 KB Output is correct
8 Correct 149 ms 512 KB Output is correct
9 Correct 147 ms 484 KB Output is correct
10 Correct 139 ms 484 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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