Submission #698563

#TimeUsernameProblemLanguageResultExecution timeMemory
698563arnevesIdeal city (IOI12_city)C++17
32 / 100
59 ms5796 KiB
/* ______ _____ _______ _ _ _______ __ _ _____ _ _ _ |_____/ | | | |____/ |______ | \ | | | | | | | \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__| . . . . . . _\/ \/_ _\/ \/_ _\/ \/_ _\/\/_ _\/\/_ _\/\/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_ / /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \ _/\/\_ _/\/\_ _/\/\_ /\ /\ /\ /\ /\ /\ ' ' ' ' ' ' */ #pragma GCC optimize ("O3") #pragma GCC target ("avx2") #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <climits> #include <cstdint> #include <cmath> #include <chrono> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <memory> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_set> #include <unordered_map> #include <vector> using namespace std; struct seg{ int id,l,r; }; void dfs(int s, int p, vector<vector<int> > &adj, vector<int> &d){ for(auto u: adj[s]){ if(u==p) continue; dfs(u,s,adj,d); d[s]+=d[u]; } } long long solve(int N, int *X, int *Y){ long long int ans=0; map<int, vector<int> >mapi; for(int i=0; i<N; i++){ mapi[X[i]].push_back(Y[i]); } int c=0; map<int, vector<seg> > comp; for(auto &u: mapi){ sort(u.second.begin(), u.second.end()); int l=u.second[0],r=l; for(int i=1; i<u.second.size(); i++){ if(u.second[i]==u.second[i-1]+1) r++; else{ comp[u.first].push_back({c,l,r}); l=r=u.second[i]; c++; } } comp[u.first].push_back({c,l,r}); c++; } vector<vector<int> > adj(c, vector<int>()); for(const auto &u: comp){ int y=u.first; if(comp[y+1].size()==0){ comp.erase(y+1); continue; } vector<seg> v1=comp[y]; vector<seg> v2=comp[y+1]; int i=0, j=0; int n=v1.size(), m=v2.size(); while(i<n && j<m) { int l=max(v1[i].l, v2[j].l); int r=min(v1[i].r, v2[j].r); if(l <= r){ adj[v1[i].id].push_back(v2[j].id); adj[v2[j].id].push_back(v1[i].id); } if(v1[i].r<v2[j].r) i++; else j++; } } vector<int> subtreesize(c); for(const auto &u: comp){ for(const seg i: u.second){ subtreesize[i.id]=i.r-i.l+1; } } dfs(0, -1, adj, subtreesize); for(int i=0; i<c; i++){ for(int j: adj[i]){ if(j>i){ int k=min(subtreesize[i], subtreesize[j]); ans+=k*(N-k); ans%=1'000'000'000; } } } return ans; } int DistanceSum(int N, int *X, int *Y) { long long ans=0; ans+=solve(N,X,Y); ans+=solve(N,Y,X); ans%=1000'000'000; return ans; }

Compilation message (stderr)

city.cpp: In function 'long long int solve(int, int*, int*)':
city.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=1; i<u.second.size(); i++){
      |                ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...