제출 #421441

#제출 시각아이디문제언어결과실행 시간메모리
421441Aldas25이상적인 도시 (IOI12_city)C++14
0 / 100
1081 ms4600 KiB
#include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr) #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; const int MAXN = 100100; const ll MOD = 1000 * 1000 * 1000; int x[MAXN], y[MAXN]; ll d[MAXN]; ll n; vi adj[MAXN]; void bfs (int st) { FOR(i, 0, n-1) d[i] = -1; queue<int> q; q.push(st); d[st] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int u : adj[v]) { if (d[u] == -1) { d[u] = d[v]+1; q.push(u); } } } } ll sub2 () { ll ans = 0; FOR(i, 0, n-1) { bfs(i); FOR(j, 0, n-1) ans += d[j]; } ans /= 2; return ans; } map<ll, ll> cntX, cntY; int DistanceSum(int N, int *X, int *Y) { n = N; FOR(i, 0, n-1) x[i] = X[i]; FOR(i, 0, n-1) y[i] = Y[i]; FOR(i, 0, n-1) FOR(j, i+1, n-1) { if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1){ adj[i].pb(j); adj[j].pb(i); } } //ll bruteAns = sub2(); FOR(i, 0, n-1) cntX[x[i]]++; FOR(i, 0, n-1) cntY[y[i]]++; ll ans = 0; ll cr = 0; for (auto p : cntX) { cr += p.s; ans += cr*(n-cr) % MOD; ans %= MOD; } cr = 0; for (auto p : cntY) { cr += p.s; ans += cr*(n-cr) % MOD; ans %= MOD; } //cout << " brute ans = " << bruteAns << " ans = " << ans << endl; return ans%MOD; } /* 15 7 5 7 6 8 3 8 4 8 5 8 6 9 3 9 4 9 5 9 6 10 3 10 4 10 5 10 6 11 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...