Submission #316034

#TimeUsernameProblemLanguageResultExecution timeMemory
316034VROOM_VARUNIdeal city (IOI12_city)C++14
100 / 100
219 ms28264 KiB
/* ID: varunra2 LANG: C++ TASK: city */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000000 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions // int calc(int *x, int n) { // ll ret = 0; // ll sum = 0; // for(ll i = 0; i < n; i++) { // ret += abs(x[i] * i - sum); // sum += x[i]; // ret %= INF; // sum %= INF; // } // return ret; // } struct dsu { VI par; VI siz; int n; void init(int _n) { n = _n; par.resize(n); iota(all(par), 0); siz.assign(n, 1); } int find(int x) { while (par[x] != par[par[x]]) par[x] = par[par[x]]; return par[x]; } bool isPar(int x) { return x == find(x); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } void pr() { debug("printing tree's dsu"); debug(siz); } }; struct tree { int n; VVI adj; dsu ds; vector<ll> sub; vector<ll> ret; int tot; void init(int _n) { n = _n; adj.resize(n); ds.init(n); ret.resize(n); sub.resize(n); } void addEdge(int u, int v) { adj[u].PB(v); adj[v].PB(u); } void cleanAdj() { trav(x, adj) { sort(all(x)); x.resize(unique(all(x)) - x.begin()); } } void genAdj(VI& a, VI& b) { VII vals(n); for (int i = 0; i < n; i++) { vals[i] = MP(a[i], b[i]); } sort(all(vals)); for (int i = 0; i < n - 1; i++) { if (vals[i].x == vals[i + 1].x and vals[i].y == vals[i + 1].y - 1) { ds.merge(i, i + 1); } } map<PII, int> mp; for (int i = 0; i < n; i++) { mp[vals[i]] = ds.find(i) + 1; } for (int i = 0; i < n; i++) { int u = ds.find(i); int ind; ind = mp[MP(vals[i].x - 1, vals[i].y)]; if (ind) { addEdge(u, ind - 1); } ind = mp[MP(vals[i].x + 1, vals[i].y)]; if (ind) { addEdge(u, ind - 1); } } cleanAdj(); tot = 0; for (int i = 0; i < n; i++) { if (i == ds.find(i)) tot++; } } void dfs(int u, int v) { sub[u] = ds.siz[u]; for (auto& x : adj[u]) { if (x == v) continue; dfs(x, u); sub[u] += sub[x]; ret[u] += sub[x] * (1ll * n - sub[x]); } return; } int calc() { dfs(0, -1); return (accumulate(all(ret), 0ll) % INF); } void pr() { debug("printing tree"); debug(adj); debug(ret); debug(sub); ds.pr(); } }; int DistanceSum(int n, int* x, int* y) { VI a(n); VI b(n); for (int i = 0; i < n; i++) { a[i] = x[i]; b[i] = y[i]; } tree hor, ver; hor.init(n); ver.init(n); hor.genAdj(a, b); ver.genAdj(b, a); int v1, v2; v1 = hor.calc(); v2 = ver.calc(); // debug(v1, v2); hor.pr(); ver.pr(); int ret = (v1 + v2) % MOD; return ret; } // int main() { // #ifndef ONLINE_JUDGE // freopen("city.in", "r", stdin); // freopen("city.out", "w", stdout); // #endif // cin.sync_with_stdio(0); // cin.tie(0); // int n; // cin >> n; // int x[n]; // int y[n]; // for (int i = 0; i < n; i++) { // cin >> x[i] >> y[i]; // } // cout << DistanceSum(n, x, y) << '\n'; // return 0; // }

Compilation message (stderr)

city.cpp: In member function 'void dsu::pr()':
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:92:5: note: in expansion of macro 'debug'
   92 |     debug("printing tree's dsu");
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:93:5: note: in expansion of macro 'debug'
   93 |     debug(siz);
      |     ^~~~~
city.cpp: In member function 'void tree::pr()':
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:175:5: note: in expansion of macro 'debug'
  175 |     debug("printing tree");
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:176:5: note: in expansion of macro 'debug'
  176 |     debug(adj);
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:177:5: note: in expansion of macro 'debug'
  177 |     debug(ret);
      |     ^~~~~
city.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
city.cpp:178:5: note: in expansion of macro 'debug'
  178 |     debug(sub);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...