Submission #168883

#	Time	Username	Problem	Language	Result	Execution time	Memory
168883		cgiosy	Ideal city (IOI12_city)	C++17	100 / 100	103 ms	21496 KiB

city

#include <bits/stdc++.h>
using namespace std;

struct pii {
	int x, y, a, b;
	bool operator<(const pii &d) const { return x<d.x || x==d.x && y<d.y; }
};
int DistanceSum(int N, int *XX, int *YY) {
	vector<pii> A(N);
	for(auto&[x,y,a,b]:A) x=*XX++, y=*YY++;
	sort(begin(A), end(A));

	vector<int> X(N), Y(N);
	int n=-1, m=-1, r=0, px=0, py=0;
	for(auto&[x,y,a,b]:A) {
		X[a=n+=x!=px || y!=py+1]++;
		px=x, py=y;
		swap(x, y);
	}
	sort(begin(A), end(A));

	px=0, py=0;
	vector<set<int>> G(N), H(N);
	for(auto&[x,y,a,b]:A) {
		if(x==px && y==py+1) G[r].insert(a), G[a].insert(r);
		Y[b=m+=x!=px || y!=py+1]++;
		px=x, py=y, r=a;
		swap(x, y);
	}
	sort(begin(A), end(A));

	px=0, py=0;
	for(auto&[x,y,a,b]:A) {
		if(x==px && y==py+1) H[r].insert(b), H[b].insert(r);
		px=x, py=y, r=b;
	}

	int s=0;
	function<void(int, int)> f1=[&](int i, int p) {
		for(int j:G[i]) if(j!=p) f1(j, i), X[i]+=X[j];
		s=(s+X[i]*long(N-X[i]))%int(1e9);
	};
	function<void(int, int)> f2=[&](int i, int p) {
		for(int j:H[i]) if(j!=p) f2(j, i), Y[i]+=Y[j];
		s=(s+Y[i]*long(N-Y[i]))%int(1e9);
	};
	f1(0, 0), f2(0, 0);
	return s;
}

Compilation message (stderr)

city.cpp: In member function 'bool pii::operator<(const pii&) const':
city.cpp:6:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  bool operator<(const pii &d) const { return x<d.x || x==d.x && y<d.y; }
                                                       ~~~~~~~^~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:10:19: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  for(auto&[x,y,a,b]:A) x=*XX++, y=*YY++;
                   ^
city.cpp:10:19: warning: variable 'y' set but not used [-Wunused-but-set-variable]
city.cpp:10:19: warning: unused variable 'a' [-Wunused-variable]
city.cpp:10:19: warning: unused variable 'b' [-Wunused-variable]
city.cpp:15:19: warning: unused variable 'b' [-Wunused-variable]
  for(auto&[x,y,a,b]:A) {
                   ^
city.cpp:33:19: warning: unused variable 'a' [-Wunused-variable]
  for(auto&[x,y,a,b]:A) {
                   ^

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45