oj.uz

Submission #363044

# Submission time Handle Problem Language Result Execution time Memory
363044 2021-02-05T03:27:36 Z eric_xiao Ideal city (IOI12_city) C++14
11 / 100
 1000 ms 5308 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;
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
unordered_set<pll,hash_pair> st;
unordered_map<pll,ll,hash_pair> dis;
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;
void BFS(pll s)
{
    queue<pll> q;
    q.push(s);
    ll i;
    dis.clear();
    dis[s] = 0;
    while(!q.empty())
    {
        auto u = q.front();
        q.pop();
        for(i = 0;i < 4;i++)
        {
            if(st.count({u.F + X[i],u.S + Y[i]}) && !dis.count({u.F + X[i],u.S + Y[i]}))
            {
                dis[{u.F + X[i],u.S + Y[i]}] = dis[u] + 1;
                q.push({u.F + X[i],u.S + Y[i]});
            }
        }
    }
    for(auto a : dis)
    {
        ans += a.S;
    }
}
int DistanceSum(int N, int *X, int *Y) {
    ll M,i,j,k;
    st.reserve(2048);
    st.max_load_factor(0.25);
    dis.reserve(2048);
    dis.max_load_factor(0.25);
    for(i = 0;i < N;i++)
    {
        all[i] = {X[i],Y[i]};
    }
    sort(all,all+N);
    for(i = N-1;i >= 0;i--)
    {
        st.insert(all[i]);
    }
    for(i = 0;i < N;i++)
    {
        BFS(all[i]);
    }
    return (int)(ans/2)%m;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Correct 15 ms 364 KB Output is correct
7 Correct 14 ms 364 KB Output is correct
8 Correct 14 ms 364 KB Output is correct
9 Correct 14 ms 364 KB Output is correct
10 Correct 19 ms 364 KB Output is correct
11 Correct 15 ms 364 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 556 KB Output is correct
2 Correct 413 ms 492 KB Output is correct
3 Execution timed out 1090 ms 620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 5308 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 1085 ms 5308 KB Time limit exceeded
2 Halted 0 ms 0 KB -