Submission #869410

#	Time	Username	Problem	Language	Result	Execution time	Memory
869410		salmon	Ideal city (IOI12_city)	C++14	32 / 100	82 ms	5468 KiB

city

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


int DistanceSum(int N, int *X, int *Y) {

    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++){
        for(int i = 0; i < N; i++){
            d[i] = -1;
        }

        queue<int> q;

        q.push(i);
        d[i] = 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;
        }
    }

    return ans/2;
}

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