Submission #869423

#	Time	Username	Problem	Language	Result	Execution time	Memory
869423		salmon	Ideal city (IOI12_city)	C++14	0 / 100	24 ms	9648 KiB

city

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


int DistanceSum(int N, int *X, int *Y) {
    int lst[100100];
    int lst1[100100];
    int prelst[100100];
    int prelst1[100100];
    int num[100100];
    map<int,int> mepx;
    map<int,int> mepy;
    map<int,int> mepx1;
    map<int,int> mepy1;
    int Nx;
    int Ny;

    for(int i = 0; i < N; i++){
        mepx[Y[i]] = max(mepx[Y[i]], X[i]);
    }

    for(int i = 0; i < N; i++){
        mepy[X[i]] = max(mepy[X[i]], Y[i]);
    }

    for(int i = 0; i < N; i++){
        mepx1[Y[i]] = min(mepx1[Y[i]], X[i]);
    }

    for(int i = 0; i < N; i++){
        mepy1[X[i]] = min(mepy1[X[i]], Y[i]);
    }


    Nx = mepy.size();
    Ny = mepx.size();

    int cont = 0;

    for(pair<int,int> ii : mepy){
        lst[cont] = ii.second - mepy1[ii.first];
        cont++;
    }

    cont = 0;

    for(pair<int,int> ii : mepx){
        lst[cont] = ii.second - mepx1[ii.first];
        cont++;
    }

    int minX = (*mepy.begin()).second;
    int maxX = (*mepy.rbegin()).second;

    int miny = (*mepx.begin()).second;
    int maxy = (*mepx.rbegin()).second;

    prelst[0] = lst[0];

    for(int i = 0; i < Nx; i++){
        prelst[i] =  prelst[i - 1] + lst[i];
    }

    prelst1[0] = lst1[0];

    for(int i = 0; i < Ny; i++){
        prelst1[i] = prelst1[i - 1] + lst1[i];
    }

    vector<int> adjlst[2100];
    set<pair<int,int>> sat;
    int d[2100];
    map<pair<int,int>,int> mep;

    for(int i = 0; i < N; i++){
        mep[make_pair(X[i],Y[i])] = i;
        sat.insert(make_pair(X[i],Y[i]));
    }

    for(int i = 0; i < N; i++){
        int x = X[i];
        int y = Y[i];

        auto it = sat.find(make_pair(x - 1,y));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x-1,y)]);
        }

        it = sat.find(make_pair(x + 1,y));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x+1,y)]);
        }

        it = sat.find(make_pair(x,y - 1));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x,y - 1)]);
        }

        it = sat.find(make_pair(x,y + 1));

        if(it != sat.end()){
            adjlst[i].push_back(mep[make_pair(x,y + 1)]);
        }
    }

    int ans = 0;

    for(int i = 0; i < N; i++){
        d[i] = -1;
    }

    queue<int> q;

    q.push(0);
    d[0] = 0;

    while(!q.empty()){
        int j = q.front();
        q.pop();

        for(int k : adjlst[j]){
            if(d[k] == -1){
                d[k] = d[j] + 1;
                q.push(k);
            }
        }
    }

    for(int i = 0; i < N; i++){
        ans += d[i];
        ans %= 1000000000;
    }

    num[0] = ans;

    int realans = ans;

    q.push(0);
    d[0] = 0;

    while(!q.empty()){
        int j = q.front();
        q.pop();

        for(int k : adjlst[j]){
            if(d[k] == -1){
                d[k] = d[j] + 1;
                q.push(k);
            }

            if(X[k] == X[j]){
                if(Y[k] > Y[j]){
                    num[k] = num[j] + prelst1[Ny] - prelst1[Y[j]] * 2;
                }
                else{
                    num[k] = num[j] - prelst1[Ny] + prelst1[Y[k]] * 2;
                }
            }
            else{
                if(X[k] > X[j]){
                    num[k] = num[j] + prelst[Nx] - prelst[Y[j]] * 2;
                }
                else{
                    num[k] = num[j] - prelst[Nx] + prelst[Y[k]] * 2;
                }
            }
            num[k] = num[k] % 1000000000;

            realans = (realans + num[k]) % 1000000000;

        }
    }


    return realans / 2;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:52:9: warning: unused variable 'minX' [-Wunused-variable]
   52 |     int minX = (*mepy.begin()).second;
      |         ^~~~
city.cpp:53:9: warning: unused variable 'maxX' [-Wunused-variable]
   53 |     int maxX = (*mepy.rbegin()).second;
      |         ^~~~
city.cpp:55:9: warning: unused variable 'miny' [-Wunused-variable]
   55 |     int miny = (*mepx.begin()).second;
      |         ^~~~
city.cpp:56:9: warning: unused variable 'maxy' [-Wunused-variable]
   56 |     int maxy = (*mepx.rbegin()).second;
      |         ^~~~
city.cpp:64:24: warning: 'lst1[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     prelst1[0] = lst1[0];
      |                  ~~~~~~^
city.cpp:58:22: warning: 'lst[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     prelst[0] = lst[0];
      |                 ~~~~~^
city.cpp:64:24: warning: 'lst1[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     prelst1[0] = lst1[0];
      |                  ~~~~~~^

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