oj.uz

답안 #477478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477478 2021-10-02T09:16:09 Z qwerasdfzxcl 이상적인 도시 (IOI12_city) C++14
100 / 100
 334 ms 16276 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 464 KB Output is correct
4 Correct 3 ms 464 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 3 ms 448 KB Output is correct
9 Correct 3 ms 464 KB Output is correct
10 Correct 3 ms 464 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2572 KB Output is correct
2 Correct 38 ms 2812 KB Output is correct
3 Correct 102 ms 6192 KB Output is correct
4 Correct 104 ms 6236 KB Output is correct
5 Correct 262 ms 11948 KB Output is correct
6 Correct 275 ms 12108 KB Output is correct
7 Correct 258 ms 11512 KB Output is correct
8 Correct 277 ms 12312 KB Output is correct
9 Correct 298 ms 12104 KB Output is correct
10 Correct 265 ms 16276 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2752 KB Output is correct
2 Correct 39 ms 2992 KB Output is correct
3 Correct 130 ms 7032 KB Output is correct
4 Correct 108 ms 6344 KB Output is correct
5 Correct 329 ms 13384 KB Output is correct
6 Correct 290 ms 11820 KB Output is correct
7 Correct 334 ms 13780 KB Output is correct
8 Correct 288 ms 11428 KB Output is correct
9 Correct 295 ms 10604 KB Output is correct
10 Correct 271 ms 10568 KB Output is correct