제출 #1241758

#제출 시각아이디문제언어결과실행 시간메모리
1241758luvlorndevIdeal city (IOI12_city)C++20
11 / 100
1094 ms1352 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int coorX[2010]; int coorY[2010]; int MOD = 1000000000; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; map<pair<int, int>, int> mp; ll bfs(int idx, int n) { queue <int> q; vector<bool> visited(2010,0); vector<int> dist(2010, 0); q.push(idx); visited[idx]=1; while (!q.empty()) { int fr = q.front(); q.pop(); // cout << fr << " " << dist[fr] << endl; int cx = coorX[fr]; int cy = coorY[fr]; for (int i = 0; i < 4; i++) { int nx = cx+dx[i]; int ny = cy+dy[i]; if (mp.count(make_pair(nx, ny))) { int nxt = mp[make_pair(nx, ny)]; if (visited[nxt] == 0) { q.push(nxt); dist[nxt] = dist[fr]+1; visited[nxt] = 1; } } } } ll sum =0 ; for (int i = 0; i < idx; i++) { sum += dist[i]; // cout << dist[i] << endl; } return sum; } int DistanceSum(int N, int *X, int *Y) { for (int i = 0; i < N; i++) { mp[make_pair(X[i], Y[i])] = i; coorX[i] = X[i]; coorY[i] = Y[i]; } ll sumtot = 0; for (int i = 0; i < N; i++) { sumtot += bfs(i, N); sumtot %= MOD; } return sumtot; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...