Submission #566774

#TimeUsernameProblemLanguageResultExecution timeMemory
566774benjaminkleynIdeal city (IOI12_city)C++17
0 / 100
97 ms4300 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; map<pair<int,int>, bool> exists; map<pair<int,int>, int> node_of; int sz[100000]; int sub_sz[100000] = {0}; bool vis[100000]; int dfs(pair<int,int> u) { vis[node_of[u]] = true; int cur_x = u.first; sub_sz[node_of[u]] = sz[node_of[u]]; while (exists[{++cur_x, u.second}] == true); while (exists[{--cur_x, u.second}] == true) { if (exists[{cur_x, u.second - 1}] == true) if (!vis[node_of[{cur_x, u.second - 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second - 1}); if (exists[{cur_x, u.second + 1}] == true) if (!vis[node_of[{cur_x, u.second + 1}]]) sub_sz[node_of[u]] += dfs({cur_x, u.second + 1}); } return sub_sz[node_of[u]]; } int solve(int N, int *X, int *Y) { exists.clear(); node_of.clear(); for (int i = 0; i < N; i++) exists[{X[i], Y[i]}] = true; int node = -1; for (int i = 0; i < N; i++) { if (node_of[{X[i], Y[i]}] != 0) continue; node_of[{X[i], Y[i]}] = ++node; int cur_x = X[i]; while (exists[{--cur_x, Y[i]}] == true) node_of[{cur_x, Y[i]}] = node; cur_x = X[i]; while (exists[{++cur_x, Y[i]}] == true) node_of[{cur_x, Y[i]}] = node; } memset(sz, 0, node); memset(sub_sz, 0, node); memset(vis, false, node); for (int i = 0; i < N; i++) sz[node_of[{X[i], Y[i]}]]++; dfs({X[0], Y[0]}); ll res = 0; for (int i = 0; i < node; i++) res += sub_sz[i] * (N - sub_sz[i]); return res; } int DistanceSum(int N, int *X, int *Y) { return solve(N, X, Y) + solve(N, Y, X); }

Compilation message (stderr)

In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from city.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int solve(int, int*, int*)' at city.cpp:52:11:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In function 'void* memset(void*, int, size_t)',
    inlined from 'int solve(int, int*, int*)' at city.cpp:53:11:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In function 'void* memset(void*, int, size_t)',
    inlined from 'int solve(int, int*, int*)' at city.cpp:54:11:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask 10 / 11

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 20 / 21

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 30 / 23

#Verdict Execution timeMemoryGrader output
Fetching results...

Subtask 40 / 45

#Verdict Execution timeMemoryGrader output
Fetching results...