# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735631 | myrcella | Ideal city (IOI12_city) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000000
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 1e5+10;
pii city[maxn];
int ans = 0;
int n;
vector <int> edge[maxn];
int sz[maxn];
map <pii,int> id;
int vis[maxn];
int dis[maxn][maxn];
void dfs(int u) {
vis[u] = 1;
for (int v:edge[u]) {
if (vis[v]==1) continue;
dfs(v);
sz[u] += sz[v];
}
// debug(sz[u]);
inc(ans,1ll*sz[u]*(n-sz[u])%mod);
}
void solve() {
memset(vis,0,sizeof(vis));
rep(i,0,maxn) while (!edge[i].empty()) edge[i].pop_back();
id.clear();
sort(city,city+n);
int tot = 0,cnt=1;
id[city[0]] = 0;
rep(i,1,n) {
if (city[i].fi == city[i-1].fi and city[i].se-1 == city[i-1].se) cnt++;
else sz[tot++] = cnt,cnt = 1;
id[city[i]] = tot;
if (id.find(MP(city[i].fi-1,city[i].se))!=id.end()) {
int tmp = id[MP(city[i].fi-1,city[i].se)];
edge[tmp].pb(tot);
edge[tot].pb(tmp);
}
}
sz[tot++] = cnt;
dfs(0);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
rep(i,0,n) city[i] = {X[i],Y[i]};
solve();
// debug(ans);
rep(i,0,n) swap(city[i].fi,city[i].se);
solve();
return ans;
}
Compilation message (stderr)
city.cpp:1:1: error: expected unqualified-id before '/' token 1 | /by szh | ^ In file included from /usr/include/c++/10/cmath:43, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity 162 | __is_null_pointer(std::nullptr_t) | ^ /usr/include/c++/10/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)' 157 | __is_null_pointer(_Type) | ^~~~~~~~~~~~~~~~~ /usr/include/c++/10/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std' 162 | __is_null_pointer(std::nullptr_t) | ^~~~~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:402:26: error: 'std::size_t' has not been declared 402 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope 403 | struct is_array<_Tp[_Size]> | ^~~~~ /usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid 403 | struct is_array<_Tp[_Size]> | ^ /usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std' 508 | struct __is_null_pointer_helper<std::nullptr_t> | ^~~~~~~~~ /usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid 508 | struct __is_null_pointer_helper<std::nullptr_t> | ^ /usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1351 | : public integral_constant<std::size_t, alignof(_Tp)> | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid 1351 | : public integral_constant<std::size_t, alignof(_Tp)> | ^ /usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1360 | : public integral_constant<std::size_t, 0> { }; | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1360:46: error: template argument 1 is invalid 1360 | : public integral_constant<std::size_t, 0> { }; | ^ /usr/include/c++/10/type_traits:1360:46: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1362:26: error: 'std::size_t' has not been declared 1362 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/10/type_traits:1363:21: error: '_Size' was not declared in this scope 1363 | struct rank<_Tp[_Size]> | ^~~~~ /usr/include/c++/10/type_traits:1363:27: error: template argument 1 is invalid 1363 | struct rank<_Tp[_Size]> | ^ /usr/include/c++/10/type_traits:1364:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { }; | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1364:65: error: template argument 1 is invalid 1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { }; | ^ /usr/include/c++/10/type_traits:1364:65: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1368:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { }; | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1368:65: error: template argument 1 is invalid 1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { }; | ^ /usr/include/c++/10/type_traits:1368:65: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1373:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1373 | : public integral_constant<std::size_t, 0> { }; | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1373:46: error: template argument 1 is invalid 1373 | : public integral_constant<std::size_t, 0> { }; | ^ /usr/include/c++/10/type_traits:1373:46: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1375:42: error: 'std::size_t' has not been declared 1375 | template<typename _Tp, unsigned _Uint, std::size_t _Size> | ^~~ /usr/include/c++/10/type_traits:1376:23: error: '_Size' was not declared in this scope 1376 | struct extent<_Tp[_Size], _Uint> | ^~~~~ /usr/include/c++/10/type_traits:1376:36: error: template argument 1 is invalid 1376 | struct extent<_Tp[_Size], _Uint> | ^ /usr/include/c++/10/type_traits:1377:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1377 | : public integral_constant<std::size_t, | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1378:24: error: '_Size' was not declared in this scope 1378 | _Uint == 0 ? _Size : extent<_Tp, | ^~~~~ /usr/include/c++/10/type_traits:1379:28: error: template argument 1 is invalid 1379 | _Uint - 1>::value> | ^ /usr/include/c++/10/type_traits:1379:28: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1384:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'? 1384 | : public integral_constant<std::size_t, | ^~~~~~ In file included from /usr/include/stdlib.h:31, from /usr/include/c++/10/bits/std_abs.h:38, from /usr/include/c++/10/cmath:47, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here 209 | typedef __SIZE_TYPE__ size_t; | ^~~~~~ In file included from /usr/include/c++/10/bits/move.h:57, from /usr/include/c++/10/bits/stl_pair.h:59, from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/type_traits:1386:31: error: template argument 1 is invalid 1386 | _Uint - 1>::value> | ^ /usr/include/c++/10/type_traits:1386:31: note: invalid template non-type parameter /usr/include/c++/10/type_traits:1975:26: error: 'std::size_t' has not been declared 1975 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/10/type_traits:1976:30: error: '_Size' was not declared in this scope 1976 | struct remove_extent<_Tp[_Size]> | ^~~~~ /usr/include/c++/10/type_traits:1976:36: error: template argument 1 is invalid 1976 | struct remove_extent<_Tp[_Size]> | ^ /usr/include/c++/10/type_traits:1988:26: error: 'std::size_t' has not been declared 1988 | template<typename _Tp, std::size_t _Size> | ^~~ /usr/include/c++/10/type_traits:1989:35: error: '_Size' was not declared in this scope 1989 | struct remove_all_extents<_Tp[_Size]> | ^~~~~ /usr/include/c++/10/type_traits:1989:41: error: template argument 1 is invalid 1989 | struct remove_all_extents<_Tp[_Size]> | ^ /usr/include/c++/10/type_traits:2047:12: error: 'std::size_t' has not been declared 2047 | template<std::size_t _Len> | ^~~ /usr/include/c++/10/type_traits:2052:23: error: '_Len' was not declared in this scope 2052 | unsigned char __data[_Len]; | ^~~~ /usr/include/c++/10/type_traits:2067:12: error: 'std::size_t' has not been declared 2067 | template<std::size_t _Len, std::size_t _Align = | ^~~ /usr/include/c++/10/type_traits:2067:30: error: 'std::size_t' has not been declared 2067 | template<std::size_t _Len, std::size_t _Align = | ^~~ /usr/include/c++/10/type_traits:2068:48: error: '_Len' was not declared in this scope 2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)> | ^~~~ /usr/include/c++/10/type_traits:2068:52: error: template argument 1 is invalid 2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)> | ^ /usr/include/c++/10/type_traits:2073:23: error: '_Len' was not declared in this scope 2073 | unsigned char __data[_Len]; | ^~~~ /usr/include/c++/10/type_traits:2074:37: error: '_Align' was not declared in this scope 2074 | struct __attribute__((__aligned__((_Align)))) { } __align; | ^~~~~~ In file included from /usr/include/c++/10/bits/stl_algobase.h:64, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/bits/stl_pair.h:92:12: error: 'std::size_t' has not been declared 92 | template<std::size_t...> | ^~~ /usr/include/c++/10/bits/stl_pair.h:449:36: error: 'std::size_t' has not been declared 449 | template<typename... _Args1, std::size_t... _Indexes1, | ^~~ /usr/include/c++/10/bits/stl_pair.h:450:36: error: 'std::size_t' has not been declared 450 | typename... _Args2, std::size_t... _Indexes2> | ^~~ /usr/include/c++/10/bits/stl_pair.h:453:27: error: '_Indexes1' was not declared in this scope 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^~~~~~~~~ /usr/include/c++/10/bits/stl_pair.h:453:36: error: expected parameter pack before '...' 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^~~ /usr/include/c++/10/bits/stl_pair.h:453:39: error: template argument 1 is invalid 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^ /usr/include/c++/10/bits/stl_pair.h:453:55: error: '_Indexes2' was not declared in this scope 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^~~~~~~~~ /usr/include/c++/10/bits/stl_pair.h:453:64: error: expected parameter pack before '...' 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^~~ /usr/include/c++/10/bits/stl_pair.h:453:67: error: template argument 1 is invalid 453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); | ^ In file included from /usr/include/c++/10/bits/stl_algobase.h:65, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/bits/stl_iterator_base_types.h:125:67: error: 'ptrdiff_t' does not name a type 125 | template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t, | ^~~~~~~~~ In file included from /usr/include/c++/10/bits/stl_algobase.h:65, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'? +++ |+#include <cstddef> 1 | // Types used in iterator implementation -*- C++ -*- In file included from /usr/include/c++/10/bits/stl_algobase.h:65, from /usr/include/c++/10/bits/specfun.h:45, from /usr/include/c++/10/cmath:1927, from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41, from city.cpp:2: /usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: error: 'ptrdiff_t' does not name a type 214 | typedef ptrdiff_t difference_type; | ^~~~~~~~~ /usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'? /usr/include/c++/10/bits/stl_iterator_base_types.h:225:15: error: 'ptrdiff_t' does not name a type 225 | typedef ptrdiff_t difference_type;