Submission #363045

#	Time	Username	Problem	Language	Result	Execution time	Memory
363045		eric_xiao	Ideal city (IOI12_city)	C++14	32 / 100	1092 ms	3820 KiB

city

#include<bits/stdc++.h>
#define ll long long
#define pll pair<int,int>
#define F first
#define S second
using namespace std;
const ll m = 1000000000;

vector<ll> G[100009];
pll all[100009];
ll X[4] = {0,1,0,-1},Y[4] {1,0,-1,0};
/*k = 0 U
  k = 1 R
  k = 2 D
  k = 4 L*/
ll ans;
ll d[100009];
ll n;
bool can(pll a,pll b)
{
    if(abs(a.F-b.F) + abs(a.S-b.S) == 1) return 1;
    return 0;
}
void BFS(ll s)
{
    queue<ll> q;
    q.push(s);
    int i;
    for(i = 0;i < n;i++) d[i] = -1;
    d[s] = 0;
    while(!q.empty())
    {
        ll u = q.front();
        q.pop();
        for(auto v : G[u])
        {
            if(d[v] < 0)
            {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    for(i = 0;i < n;i++) ans += d[i];
}
int DistanceSum(int N, int *X, int *Y) {
    n = N;
    ll M,i,j,k;

    for(i = 0;i < N;i++)
    {
        all[i] = {X[i],Y[i]};
    }
    for(i = 0;i < N;i++)
    {
        for(j = 0;j < N;j++)
        {
            if(can(all[i],all[j]))
            {
                G[i].push_back(j);
            }
        }
    }
    for(i = 0;i < N;i++) BFS(i);
    return (int)((ans/2)%m);
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:48:8: warning: unused variable 'M' [-Wunused-variable]
   48 |     ll M,i,j,k;
      |        ^
city.cpp:48:14: warning: unused variable 'k' [-Wunused-variable]
   48 |     ll M,i,j,k;
      |              ^

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