oj.uz

Submission #363045

# Submission time Handle Problem Language Result Execution time Memory
363045 2021-02-05T03:33:29 Z eric_xiao Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 3820 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2924 KB Output is correct
2 Correct 34 ms 2796 KB Output is correct
3 Correct 77 ms 2796 KB Output is correct
4 Correct 78 ms 2816 KB Output is correct
5 Correct 131 ms 3072 KB Output is correct
6 Correct 140 ms 2924 KB Output is correct
7 Correct 139 ms 2924 KB Output is correct
8 Correct 142 ms 2924 KB Output is correct
9 Correct 141 ms 2924 KB Output is correct
10 Correct 137 ms 2796 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 3820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 3792 KB Time limit exceeded
2 Halted 0 ms 0 KB -