Submission #869393

#	Time	Username	Problem	Language	Result	Execution time	Memory
869393		salmon	Ideal city (IOI12_city)	C++14	0 / 100	16 ms	5716 KiB

city

#include <bits/stdc++.h>
using namespace std;
vector<int> adjlst[2100];
set<pair<int,int>> sat;
int d[2100];
map<pair<int,int>,int> mep;

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

    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() && (*it).first == x - 1 && (*it).second == y){
            adjlst[i].push_back(mep[make_pair(x-1,y)]);
        }

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

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

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

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

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

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

    long long 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[i] + 1;
                    q.push(k);
                }
            }
        }

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

    return ans;
}

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