제출 #424034

#제출 시각아이디문제언어결과실행 시간메모리
424034cfalas이상적인 도시 (IOI12_city)C++17
0 / 100
1098 ms6416 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000000 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) vi a, b; ii diag[4] = {{0,-1}, {0,1}, {-1,0}, {1,0}}; struct pair_hash { inline std::size_t operator()(const std::pair<int,int> & v) const { return v.first*31 ^ v.second; } }; int DistanceSum(int n, int *X, int *Y) { map<ii, vector<ii> > adj; FOR(i,n){ FOA(v,diag){ ii x = {v.F+X[i], v.S+Y[i]}; adj[{X[i], Y[i]}].push_back(x); } } int ans=0; FOR(i,n){ // bfs from i unordered_set<ii, pair_hash> used; queue<ii> q; q.push({X[i], Y[i]}); used.insert({X[i], Y[i]}); q.push({-1,-1}); int d=0; //cout<<X[i]<<" "<<Y[i]<<": "<<endl; while(q.size()>1){ ii t= q.front(); q.pop(); if(t.F==-1 && t.S==-1){ d++; q.push({-1,-1}); continue; } //cout<<t.F<<" "<<t.S<<" "<<d<<endl; ans+=d; ans%=MOD; FOA(x, adj[t]){ if(!used.count(x)){ q.push(x); used.insert(x); } } } } return ans/2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...