Submission #761796

#TimeUsernameProblemLanguageResultExecution timeMemory
761796fatemetmhrIdeal city (IOI12_city)C++17
100 / 100
167 ms35404 KiB
// ~ Be Name Khoda ~ // #include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC target("avx2") //#pragma GCC optimize("unroll-loops,Ofast") using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define fi first #define se second const int maxn = 1e6 + 10; const int maxn5 = 1e5 + 10; const int maxnt = 1.2e6 + 10; const int maxn3 = 2e3 + 10; const int mod = 2e9; const ll inf = 1e18; ll ans = 0; vector <int> avx, av[maxn5]; map <int, int> inner[maxn5]; int ptx[maxn5], par[maxn5]; inline void fix(ll &a){ if(a >= mod) a -= mod; if(a < 0) a += mod; } struct __node{ vector <int> adj; int n, inin; ll dissum, dissumup, nup; inline void clear(){ n = inin = 0; dissum = dissumup = nup = 0; adj.clear(); } inline void rebuild_adj(){ sort(all(adj)); adj.resize(unique(all(adj)) - adj.begin()); adj.shrink_to_fit(); } inline void sumup(int ty){ //cout << "here " << ty << ' ' << dissum << ' ' << n << ' ' << dissumup << ' ' << nup << endl; if(ty != -1){ fix(dissum += dissumup); n += nup; } fix(ans += dissum * inin % mod); //cout << "then " << dissum << ' ' << n << ' ' << inin << ' ' << ans << endl; } } node[maxn5], up[maxn5], tmp; void dfs_up(int v){ //cout << "aha " << v << ' ' << par[v] << ' ' << node[v].n << endl; for(auto u : node[v].adj) if(u != par[v]){ par[u] = v; dfs_up(u); fix(node[v].dissum += node[u].dissum); fix(node[v].dissum += node[u].n); node[v].n += node[u].n; } } void dfs_dw(int v){ //cout << "summing up " << v << endl; node[v].sumup(par[v]); for(auto u : node[v].adj) if(u != par[v]){ fix(node[u].dissumup = node[v].dissum + node[v].n); fix(node[u].dissumup -= node[u].dissum); fix(node[u].dissumup -= node[u].n); fix(node[u].dissumup -= node[u].n); node[u].nup = node[v].n - node[u].n; dfs_dw(u); } } inline int solve(int n, int *x, int *y){ ans = 0; avx.clear(); for(int i = 0; i < n; i++) avx.pb(x[i]); sort(all(avx)); avx.resize(unique(all(avx)) - avx.begin()); for(int i = 0; i < avx.size(); i++){ av[i].clear(); inner[i].clear(); } for(int i = 0; i < n; i++){ ptx[i] = lower_bound(all(avx), x[i]) - avx.begin(); av[ptx[i]].pb(y[i]); } int newid = 0; for(int i = 0; i < avx.size(); i++){ sort(all(av[i])); int last = 0; for(int j = 1; j < av[i].size(); j++){ if(av[i][j] != av[i][j - 1] + 1){ node[newid].clear(); node[newid].n = node[newid].inin = j - last; for(int k = last; k < j; k++) inner[i][av[i][k]] = newid; newid++; last = j; } } node[newid].clear(); node[newid].n = node[newid].inin = int(av[i].size()) - last; for(int k = last; k < av[i].size(); k++) inner[i][av[i][k]] = newid; newid++; } for(int i = 0; i < n; i++){ int k = inner[ptx[i]][y[i]]; if(ptx[i] && inner[ptx[i] - 1].find(y[i]) != inner[ptx[i] - 1].end()) node[k].adj.pb(inner[ptx[i] - 1][y[i]]); if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end()) node[k].adj.pb(inner[ptx[i] + 1][y[i]]); } for(int i = 0; i < newid; i++) node[i].rebuild_adj(); par[0] = -1; dfs_up(0); dfs_dw(0); return ans; } int DistanceSum(int n, int *x, int *y){ ll ans = solve(n, x, y); //cout << "here " << ans << endl; ans = (ans + solve(n, y, x)); //cout << "now " << ans << endl; return (ans % mod) / 2; }

Compilation message (stderr)

city.cpp: In function 'int solve(int, int*, int*)':
city.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < avx.size(); i++){
      |                    ~~^~~~~~~~~~~~
city.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < avx.size(); i++){
      |                    ~~^~~~~~~~~~~~
city.cpp:110:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int j = 1; j < av[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~
city.cpp:122:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int k = last; k < av[i].size(); k++)
      |                           ~~^~~~~~~~~~~~~~
city.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end())
      |            ~~~~~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...