Submission #170894

#TimeUsernameProblemLanguageResultExecution timeMemory
170894AlexLuchianovIdeal city (IOI12_city)C++14
100 / 100
968 ms39928 KiB
#include <map> #include <vector> #include <algorithm> #include <iostream> #include <stack> #include <unordered_map> using ll = long long; int const nmax = 100000; int const modulo = 1000000000; int const iplus[4] = {0, 0, 1, -1}; int const jplus[4] = {1, -1, 0, 0}; #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) < (b)) ? (b) : (a)) struct Point{ int x; int y; bool operator < (Point const &a) const{ if(x != a.x) return x < a.x; else return y < a.y; } }; void normalize(std::vector<Point> &v){ int xmin = v[0].x, ymin = v[0].y; for(int i = 1; i < v.size(); i++){ xmin = MIN(xmin, v[i].x); ymin = MIN(ymin, v[i].y); } for(int i = 0; i < v.size(); i++){ v[i].x -= xmin; v[i].y -= ymin; } } std::map<std::pair<int,int>, int> cell; namespace Dsu{ int mult[1 + nmax]; int sz[1 + nmax]; void initialize(int n){ for(int i = 0; i <= n; i++) { mult[i] = i; sz[i] = 1; } } int jump(int a){ if(mult[a] != a) return jump(mult[a]); else return a; } void unite(int gala, int galb){ gala = jump(gala); galb = jump(galb); if(sz[galb] < sz[gala]) std::swap(gala, galb); if(gala != galb){ mult[gala] = galb; sz[galb] += sz[gala]; } } } std::vector<Point> line[1 + nmax]; std::map<Point, int> id; std::unordered_map<int, int> leftextrem, leftextrem2; int dp[1 + nmax], dp2[1 + nmax]; int cost[1 + nmax], seen[1 + nmax]; std::vector<int> g[1 + nmax]; void dfs(int node, int parent){ //std::cout << node << " " << parent << '\n' seen[node] = 1; for(int h = 0; h < g[node].size(); h++){ int to = g[node][h]; if(to != parent) { dfs(to, node); cost[node] += cost[to]; } } } int dfs2(int node, int parent, int total){ int result = 1LL * (total - cost[node]) * cost[node] % modulo; for(int h = 0; h < g[node].size(); h++){ int to = g[node][h]; if(to != parent){ result += dfs2(to, node, total); if(modulo <= result) result -= modulo; } } return result; } int solveline(int x){ std::vector<int> nodes; //std::cout << "|"; for(int i = 0; i < line[x].size(); i++){ Point curr = line[x][i]; g[id[curr]].clear(); if(id[curr] == leftextrem[id[curr]]) { cost[id[curr]] = dp[id[curr]]; nodes.push_back(id[curr]); } } for(int i = 0; i < line[x + 1].size(); i++){ Point curr = line[x + 1][i]; g[id[curr]].clear(); if(id[curr] == leftextrem2[id[curr]]) { cost[id[curr]] = dp2[id[curr]]; nodes.push_back(id[curr]); } } //std::cout << "%"; int result = 0; for(int i = 0; i < line[x].size(); i++){ Point curr = line[x][i]; if(0 < cell[{x + 1, curr.y}] && (0 == cell[{x, curr.y - 1}] || 0 == cell[{x + 1, curr.y - 1}])) { int gala = leftextrem2[cell[{x + 1, curr.y}]], galb = leftextrem[id[curr]]; g[galb].push_back(gala); g[gala].push_back(galb); //std::cout << "edge " << gala << " " << galb << '\n'; } } //std::cout <<"^"; for(int i = 0; i < nodes.size(); i++){ int node = nodes[i]; seen[node] = 0; } // std::cout << "%"; for(int i = 0; i < nodes.size(); i++){ int node = nodes[i]; if(seen[node] == 0){ dfs(node, -1); // std::cout << node << " " << cost[node] << '\n'; result += dfs2(node, -1, cost[node]); if(modulo <= result) result -= modulo; } } // std::cout << ":" << x << " " << result << '\n' << '\n'; return result ; } std::unordered_map<int,int> leftsmall; int solve(std::vector<Point> v){ int n = v.size(); std::sort(v.begin(), v.end()); for(int i = 0; i < n; i++) dp[i] = dp2[i] = 0; /* for(int i = 0; i < n; i++) std::cout << v[i].x << " " << v[i].y << '\n'; std::cout << '\n'; */ leftextrem.clear(); leftextrem2.clear(); leftsmall.clear(); id.clear(); cell.clear(); for(int i = 0; i < n; i++) line[i].clear(); for(int i = 0; i < n; i++) { line[v[i].x].push_back(v[i]); id[v[i]] = i + 1; } Dsu::initialize(n); for(int i = 0; i < n; i++){ for(int j = 0; j < line[i].size(); j++){ Point curr = line[i][j]; cell[{curr.x, curr.y}] = id[curr]; if(0 < cell[{curr.x, curr.y - 1}]) Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]); if(0 < cell[{curr.x - 1, curr.y}]) Dsu::unite(id[curr], cell[{curr.x - 1, curr.y}]); } leftsmall.clear(); for(int j = 0; j < line[i].size(); j++){ Point curr = line[i][j]; dp[id[curr]] = Dsu::sz[Dsu::jump(id[curr])]; if(0 == leftsmall[Dsu::jump(id[curr])]) leftsmall[Dsu::jump(id[curr])] = id[curr]; leftextrem[id[curr]] = leftsmall[Dsu::jump(id[curr])]; } } // std::cout << ":"; Dsu::initialize(n); for(int i = n - 1; 0 <= i; i--){ for(int j = 0; j < line[i].size(); j++){ Point curr = line[i][j]; cell[{curr.x, curr.y}] = id[curr]; if(0 < cell[{curr.x, curr.y - 1}]) Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]); if(0 < cell[{curr.x + 1, curr.y}]) Dsu::unite(id[curr], cell[{curr.x + 1, curr.y}]); } leftsmall.clear(); for(int j = 0; j < line[i].size(); j++){ Point curr = line[i][j]; dp2[id[curr]] = Dsu::sz[Dsu::jump(id[curr])]; if(0 == leftsmall[Dsu::jump(id[curr])]) leftsmall[Dsu::jump(id[curr])] = id[curr]; leftextrem2[id[curr]] = leftsmall[Dsu::jump(id[curr])]; } } int result = 0; for(int i = 0; i < n; i++) { result += solveline(i); if(modulo <= result) result -= modulo; } return result; } int DistanceSum(int N, int *X, int *Y) { std::vector<Point> v(N); //std::cout << '\n'; for(int i = 0; i < N; i++) { v[i].x = X[i]; v[i].y = Y[i]; } normalize(v); int result = 0; result += solve(v); //return result; for(int i = 0; i < N; i++) std::swap(v[i].x, v[i].y); result = (result + solve(v)) % modulo; return result; }

Compilation message (stderr)

city.cpp: In function 'void normalize(std::vector<Point>&)':
city.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < v.size(); i++){
                  ~~^~~~~~~~~~
city.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
city.cpp: In function 'void dfs(int, int)':
city.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int dfs2(int, int, int)':
city.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int solveline(int)':
city.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x + 1].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~
city.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < line[x].size(); i++){
                  ~~^~~~~~~~~~~~~~~~
city.cpp:146:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++){
                  ~~^~~~~~~~~~~~~~
city.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++){
                  ~~^~~~~~~~~~~~~~
city.cpp: In function 'int solve(std::vector<Point>)':
city.cpp:201:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:211:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:223:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
city.cpp:233:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < line[i].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...