제출 #167092

#제출 시각아이디문제언어결과실행 시간메모리
167092Charis02이상적인 도시 (IOI12_city)C++14
0 / 100
47 ms5852 KiB
#include<iostream> #include<vector> #include<set> #include<cmath> #include<map> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define MAXN 200000 using namespace std; ll n,mod=1000000000; pi ar[MAXN]; map < pi,bool > grid; ll dx[] = {-1,1,0,0}; ll dy[] = {0,0,1,-1}; pi xcords; pi ycords; map < pi,bool > vis; void dfs(pi cur) { vis[cur]=true; xcords.first = min(xcords.first,cur.first); ycords.first = min(ycords.first,cur.second); xcords.second = max(xcords.second,cur.first); ycords.second = max(ycords.second,cur.second); rep(d,0,4) { pi neo = cur; neo.first+=dx[d]; neo.second+=dy[d]; if(!vis[neo] && grid[neo]) { dfs(neo); } } return; } ll expo(ll v,ll e) { if(e == 0) return 1; if(e == 1) return v; ll x = expo(v,e/2); x =(x*x)%mod; if(e%2==1) x=(x*v)%mod; return x; } ll inverse(ll x) { return expo(x,mod-2); } ll calculate_sum() { ll w = xcords.second-xcords.first+1; ll h = ycords.second-ycords.first+1; ll res = ((((w-1)*w*(w+1))/6*expo(h,2))%mod + (((h-1)*h*(h+1))/6*expo(w,2))%mod); return res; } int DistanceSum(int N, int *X, int *Y) { // cin >> n; n=N; rep(i,0,n) { ar[i].first =X[i]; ar[i].second=Y[i]; //cin >> ar[i].first>>ar[i].second; grid[mp(ar[i].first,ar[i].second)] = true; } xcords.first = ar[0].first; xcords.second = ar[0].first; ycords.first = ar[0].second; ycords.second = ar[0].second; dfs(ar[0]); return calculate_sum(); } /* 6 0 0 0 1 0 2 1 2 1 1 1 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...