Submission #412985

#TimeUsernameProblemLanguageResultExecution timeMemory
412985biggIdeal city (IOI12_city)C++14
0 / 100
35 ms12004 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9; const int MAXN = 3e5; map<pair<int, int>, int > m[3]; ll ans = 0; ll n; vector<int> grafo[MAXN]; vector<pair<int, int> > v[3]; ll w[MAXN]; ll dfs(int x, int p){ ll anslc = w[x]; for(int v: grafo[x]){ if(v == p) continue; // printf("%d %d\n", x, v); ll baixo = dfs(v,x); ans += baixo*(n-baixo); ans %= MOD; anslc += baixo; } return anslc; } int naux; int DistanceSum(int N, int *X, int *Y) { n = N; for(int aux = 0; aux < 2; aux++ ){ int minx = (1<<30), manx = 0; int tam = -1; for(int i = 0; i < N; i++){ if(aux) swap(X[i], Y[i]); minx = min(minx, X[i]), manx = max(manx, Y[i]); v[aux].push_back({X[i], Y[i]}); } sort(v[aux].begin(), v[aux].end()); int it1 = 0; printf("%d\n", aux); while(it1 < v[aux].size()){ int l = v[aux][it1].second; naux++; int r = v[aux][it1].second; set<int> jaachei; m[aux][{v[aux][it1].first, v[aux][it1].second}] = naux; if(m[aux][{v[aux][it1].first-1, v[aux][it1].second}]){ jaachei.insert(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]); grafo[naux].push_back(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]); grafo[m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]].push_back(naux); } while(it1 + 1 < v[aux].size() && v[aux][it1+1].first == v[aux][it1].first && v[aux][it1+1].second == v[aux][it1].second + 1){ it1++; m[aux][{v[aux][it1].first, v[aux][it1].second}] = naux; r = v[aux][it1].second; if(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}] && jaachei.find(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]) == jaachei.end()){ jaachei.insert(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]); grafo[naux].push_back(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]); grafo[m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]].push_back(naux); } } w[naux] = r - l + 1; // printf("%d %d %d\n",r, l, naux); it1++; } dfs(naux,naux); } return ans; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(it1 < v[aux].size()){
      |               ~~~~^~~~~~~~~~~~~~~
city.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while(it1 + 1 < v[aux].size() && v[aux][it1+1].first == v[aux][it1].first && v[aux][it1+1].second == v[aux][it1].second + 1){
      |                   ~~~~~~~~^~~~~~~~~~~~~~~
city.cpp:32:13: warning: unused variable 'tam' [-Wunused-variable]
   32 |         int tam = -1;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...