oj.uz

Submission #168883

# Submission time Handle Problem Language Result Execution time Memory
168883 2019-12-16T22:45:58 Z cgiosy Ideal city (IOI12_city) C++17
100 / 100
 103 ms 21496 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2936 KB Output is correct
2 Correct 14 ms 3192 KB Output is correct
3 Correct 34 ms 7160 KB Output is correct
4 Correct 34 ms 7288 KB Output is correct
5 Correct 67 ms 13820 KB Output is correct
6 Correct 69 ms 13944 KB Output is correct
7 Correct 68 ms 14328 KB Output is correct
8 Correct 68 ms 13816 KB Output is correct
9 Correct 72 ms 14340 KB Output is correct
10 Correct 73 ms 19576 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4472 KB Output is correct
2 Correct 17 ms 4088 KB Output is correct
3 Correct 47 ms 10788 KB Output is correct
4 Correct 41 ms 9464 KB Output is correct
5 Correct 102 ms 21244 KB Output is correct
6 Correct 79 ms 16888 KB Output is correct
7 Correct 103 ms 21496 KB Output is correct
8 Correct 81 ms 17016 KB Output is correct
9 Correct 78 ms 16072 KB Output is correct
10 Correct 76 ms 15864 KB Output is correct