Submission #251212

#	Time	Username	Problem	Language	Result	Execution time	Memory
251212		eohomegrownapps	Ideal city (IOI12_city)	C++14	32 / 100	744 ms	640 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int m = 1000000000;
unordered_set<ll> s_orig;

ll hashval(int x, int y){
    return x*(1LL<<31)+y;
}

ll bfs(int startx, int starty){
    unordered_set<ll> unvisited = s_orig;
    unvisited.erase(hashval(startx,starty));
    queue<pair<pair<int,int>,ll>> q;
    q.push({{startx,starty},0});
    ll total = 0;
    while (q.size()>0){
        auto f = q.front();
        q.pop();
        int x = f.first.first;
        int y = f.first.second;
        int dist = f.second;
        for (int i = 0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            auto f = unvisited.find(hashval(nx,ny));
            if (f!=unvisited.end()){
                unvisited.erase(f);
                total+=dist+1;
                q.push({{nx,ny},dist+1});
            }
        }
    }
    return total;
}

int subtask2(int n, int *x, int *y){
    for (int i = 0; i<n; i++){
        s_orig.insert(hashval(x[i],y[i]));
    }
    ll tot = 0;
    for (int i = 0; i<n; i++){
        tot += bfs(x[i],y[i]);
    }
    tot/=2;
    return tot%m;
}

int DistanceSum(int n, int *x, int *y) {
    if (n<=2000){
        return subtask2(n,x,y);
    }
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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