제출 #166989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166989		Charis02	이상적인 도시 (IOI12_city)	C++14	0 / 100	49 ms	5816 KiB

city

#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)%mod)*((h*h)%mod))%mod*(w+1))%mod + (((((h-1)*h)%mod)*((w*w)%mod))%mod*(h+1))%mod)*inverse(6)%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
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45