Submission #477478

#	Time	Username	Problem	Language	Result	Execution time	Memory
477478		qwerasdfzxcl	Ideal city (IOI12_city)	C++14	100 / 100	334 ms	16276 KiB

city

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 1e9;
struct DSU{
    int path[100100];
    void init(int n){
        for (int i=1;i<=n;i++) path[i] = i;
    }
    int find(int x){
        if (x==path[x]) return x;
        return path[x] = find(path[x]);
    }
    void merge(int x, int y){
        path[find(x)] = find(y);
    }
}dsu;
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;
bool adj[100100][4], visited[100100];

int dfs(int s){
    //printf("%d\n", s);
    visited[s] = 1;
    int ret = 1;
    for (int k=0;k<4;k++) if (adj[s][k]){
        int nx = X[s] + dx[k], ny = Y[s] + dy[k];
        int j = st[{nx, ny}];
        if (visited[j]) continue;
        int tmp = dfs(j);
        if (k>1) ans = (ans+(ll)tmp*(n-tmp))%MOD;
        ret += tmp;
    }
    return ret;
}

void build_st(){
    dsu.init(n);
    for (int i=1;i<=n;i++){
        for (int j=0;j<4;j++) adj[i][j] = 0;
        visited[i] = 0;
    }
    for (int i=1;i<=n;i++){
        int x = X[i], y = Y[i];
        int nx = x + dx[0], ny = y + dy[0];
        int j = st[{nx, ny}];
        if (j && dsu.find(i) != dsu.find(j)){
            dsu.merge(i, j);
            adj[i][0] = 1;
            adj[j][1] = 1;
            //printf(" %d %d\n", i, j);
        }
    }
    for (int i=1;i<=n;i++){
        int x = X[i], y = Y[i];
        int nx = x + dx[2], ny = y + dy[2];
        int j = st[{nx, ny}];
        if (j && dsu.find(i) != dsu.find(j)){
            dsu.merge(i, j);
            adj[i][2] = 1;
            adj[j][3] = 1;
            //printf(" %d %d\n", i, j);
        }
    }
    /*for (int i=1;i<=n;i++) printf("%d ", dsu.find(i));
    printf("\n");*/
}

int DistanceSum(int N, int *x, int *y) {
    ans = 0;
    n = N;
    X = x-1, Y = y-1;
    for (int i=0;i<n;i++) st[{x[i], y[i]}] = i+1;
    build_st();
    dfs(st[{X[1], Y[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;
    build_st();
    dfs(st[{X[1], Y[1]}]);
    return ans;
}

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