Submission #147188

#	Time	Username	Problem	Language	Result	Execution time	Memory
147188		jh05013	Ideal city (IOI12_city)	C++17	32 / 100	152 ms	1144 KiB

city

#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

vector<int> bfs(vector<vector<int>> &adj, int v){
    vector<int> dist(adj.size(), -1); dist[v] = 0;
    queue<int> Q({v});
    while(!Q.empty()){
        int p = Q.front(); Q.pop();
        for(int q: adj[p]) if(dist[q] == -1){
            dist[q] = dist[p] + 1;
            Q.push(q);
        }
    }
    return dist;
}

const int MOD = 1000000000;
int DistanceSum(int N, int *X, int *Y){
    assert (N <= 2000);
    vector<vector<int>> adj(N);
    for(int i=0; i<N; i++) for(int j=i+1; j<N; j++){
        if(abs(X[i]-X[j]) + abs(Y[i]-Y[j]) > 1) continue;
        adj[i].push_back(j), adj[j].push_back(i);
    }
    int ans = 0;
    for(int i=0; i<N; i++){
        vector<int> dist = bfs(adj, i);
        for(int j=i+1; j<N; j++) ans = (ans + dist[j]) % MOD;
    }
    return ans;
}

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