제출 #124996

#제출 시각아이디문제언어결과실행 시간메모리
124996RockyB이상적인 도시 (IOI12_city)C++17
100 / 100
367 ms18516 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int mod = (int)1e9; int n; int ans; map < pair <int, int>, int> used, a; int dfs(int x, int y) { int len = 0; vector < pair <int, int > > go; int ptr = y - 1; while (a.count({x, ptr + 1})) { ++len, ++ptr; for (int i = -1; i <= 1; i += 2) { if (a.count({x + i, ptr}) && !used.count({x + i, ptr})) { go.push_back({x + i, ptr}); } } used[{x, ptr}] = 1; } ptr = y; while (a.count({x, ptr - 1})) { ++len, --ptr; for (int i = -1; i <= 1; i += 2) { if (a.count({x + i, ptr}) && !used.count({x + i, ptr})) { go.push_back({x + i, ptr}); } } used[{x, ptr}] = 1; } for (auto it : go) { if (!used.count(it)) { len += dfs(it.f, it.s); } } ans += len * 1ll * (n - len) % mod; ans %= mod; return len; } int dfs1(int x, int y) { int len = 0; vector < pair <int, int > > go; int ptr = x - 1; while (a.count({ptr + 1, y})) { ++len, ++ptr; for (int i = -1; i <= 1; i += 2) { if (a.count({ptr, y + i}) && !used.count({ptr, y + i})) { go.push_back({ptr, y + i}); } } used[{ptr, y}] = 1; } ptr = x; while (a.count({ptr - 1, y})) { ++len, --ptr; for (int i = -1; i <= 1; i += 2) { if (a.count({ptr, y + i}) && !used.count({ptr, y + i})) { go.push_back({ptr, y + i}); } } used[{ptr, y}] = 1; } for (auto it : go) { if (!used.count(it)) { len += dfs1(it.f, it.s); } } ans += len * 1ll * (n - len) % mod; ans %= mod; return len; } int DistanceSum(int N, int *X, int *Y) { n = N; // copy finished for (int i = 0; i < N; i++) { a[{X[i], Y[i]}] = 1; } dfs(X[0], Y[0]); used.clear(); dfs1(X[0], Y[0]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...