Submission #477464

#	Time	Username	Problem	Language	Result	Execution time	Memory
477464		qwerasdfzxcl	Ideal city (IOI12_city)	C++14	0 / 100	47 ms	3832 KiB

city

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 1e9;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int *X, *Y, n;
ll ans;

map<pair<int, int>, int> st;
int dfs(int x, int y){
    int ret = 1;
    st[{x, y}] = 1;
    for (int k=0;k<4;k++){
        int nx = x + dx[k], ny = y + dy[k];
        if (st[{nx, ny}]!=-1) continue;
        int tmp = dfs(nx, ny);
        if (k>=2) ans = (ans+(ll)tmp*(n-tmp))%MOD;
        ret += tmp;
    }
    return ret;
}

int DistanceSum(int N, int *x, int *y) {
    ans = 0;
    n = N;
    X = x, Y = y;
    for (int i=0;i<n;i++) st[{x[i], y[i]}] = -1;
    dfs(X[0], Y[0]);
    for (int i=0;i<n;i++) st[{x[i], y[i]}] = -1;
    dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
    dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;
    dfs(X[0], Y[0]);
    return ans;
}

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