Submission #363119

#TimeUsernameProblemLanguageResultExecution timeMemory
363119Kevin_Zhang_TWIdeal city (IOI12_city)C++17
100 / 100
393 ms20420 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 300010, inf = 1e9; int N; vector<int> edge[MAX_N]; struct dsu { vector<int> g, sz; dsu(int n) { g.resize(n), sz.resize(n, 1), iota(AI(g), 0); } int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); } bool M(int a, int b) { a = F(a), b = F(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); return sz[a] += sz[b], g[b] = a, true; } int S(int i) { return sz[F(i)]; } int operator()(int i) { return F(i); } }; ll subsz[MAX_N]; ll dfs(int x, ll allsz, int lst = -1) { ll res = 0; for (int u : edge[x]) if (u != lst) { res += dfs(u, allsz, x); subsz[x] += subsz[u]; } return res += subsz[x] * (allsz - subsz[x]); } ll cal(int N, int *X, int *Y) { dsu D(N); int sz = N; vector<pair<int,int>> alle; { map<int, vector<pair<int,int>>> col; for (int i = 0;i < N;++i) col[ X[i] ].pb( Y[i], i ); for (auto &[_, vec] : col) { sort(AI(vec)); for (int i = 1;i < vec.size();++i) { if (vec[i].first - vec[i-1].first == 1) sz -= D.M(vec[i].second, vec[i-1].second); } } } map<pair<int,int>, int> loc; auto update = [&](int id, int x, int y) { if (loc.count({x, y})) { int bid = loc[{x, y}]; int a = D(id), b = D(bid); if (a > b) swap(a, b); alle.pb(a, b); } }; for (int i = 0;i < N;++i) { int x = X[i], y = Y[i]; update(i, x+1, y), update(i, x-1, y); loc[{x, y}] = i; } sort(AI(alle)); alle.resize(unique(AI(alle)) - begin(alle)); DE(alle.size(), sz); assert(alle.size() + 1 == sz); for (int i = 0;i < N;++i) { edge[i].clear(); subsz[i] = D.S(i); } for (auto [a, b] : alle) edge[a].pb(b), edge[b].pb(a); return dfs(D(0), N); } int DistanceSum(int N, int *X, int *Y) { ll res = cal(N, X, Y) + cal(N, Y, X); return res % 1'000'000'000; }

Compilation message (stderr)

city.cpp: In function 'll cal(int, int*, int*)':
city.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 1;i < vec.size();++i) {
      |                   ~~^~~~~~~~~~~~
city.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
city.cpp:80:2: note: in expansion of macro 'DE'
   80 |  DE(alle.size(), sz);
      |  ^~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from city.cpp:1:
city.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |  assert(alle.size() + 1 == sz);
      |         ~~~~~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...