Submission #481888

#	Time	Username	Problem	Language	Result	Execution time	Memory
481888		Haruto810198	Ideal city (IOI12_city)	C++17	32 / 100	107 ms	3856 KiB

city

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 2010;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int n;
map<pii, int> mp;
vi edge[MAX];
int res;

int dis[MAX];
queue<int> qu;

int bfs(int st){
    FOR(i, 0, n-1, 1){
        dis[i] = INF;
    }
    dis[st] = 0;

    qu.push(st);
    while(!qu.empty()){
        int v = qu.front();
        qu.pop();
        for(int i : edge[v]){
            if(dis[i] == INF){
                dis[i] = dis[v] + 1;
                qu.push(i);
            }
        }
    }

    int ret = 0;
    FOR(i, 0, n-1, 1){
        ret += dis[i];
    }
    return ret;
}

int DistanceSum(int N, int *X, int *Y){
    n = N;

    FOR(i, 0, N-1, 1){
        mp[mkp(X[i], Y[i])] = i;
        cerr<<X[i]<<" "<<Y[i]<<endl;
    }

    FOR(i, 0, N-1, 1){
        FOR(j, 0, 3, 1){
            pii pt = mkp(X[i] + dx[j], Y[i] + dy[j]);
            if(mp.find(pt) != mp.end()) edge[i].pb(mp[pt]);
            //if(mp.find(pt) != mp.end()) cerr<<"edge "<<i<<", "<<j<<": "<<1<<endl;
            //else cerr<<"edge "<<i<<", "<<j<<": "<<0<<endl;
        }
    }

    FOR(i, 0, N-1, 1){
        res += bfs(i);
        //cerr<<"bfs("<<i<<") = "<<bfs(i)<<endl;
    }

    res /= 2;

    return res;
}

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