oj.uz

Submission #26010

# Submission time Handle Problem Language Result Execution time Memory
26010 2017-06-26T08:54:59 Z kajebiii 개구리 (KOI13_frog) C++14
22 / 22
 206 ms 9840 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e5 + 100;

struct RT{
	int x, y, ix;
	RT() : x(0), y(0), ix(0) {}
	RT(int xx, int yy, int ii) : x(xx), y(yy), ix(ii) {}
};
bool sortX(RT a, RT b) {
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool sortY(RT a, RT b) {
	if(a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

int N, R, S[MAX_N], K;
vector<RT> Rs;
vector<int> Ed[MAX_N];

void makeGraph() {
	multiset<pi> Ys;
//	for(int i=0; i<N; i++) printf("[%d %d] ", Rs[i].x, Rs[i].y); puts("");
	for(int i=0, l=0, r=0; i<N; i++) {
		while(r < N && Rs[r].x <= Rs[i].x + R + K) Ys.insert(pi(Rs[r].y, Rs[r].ix)), r++;
		while(l < N && Rs[l].x <= Rs[i].x + R) Ys.erase(Ys.find(pi(Rs[l].y, Rs[l].ix))), l++;
//		printf("[%d]\n", i); for(pi e : Ys) printf("(%d %d) ", e.one, e.two); puts("");
		int ix = Rs[i].ix;
		int co[2] = {Rs[i].y, Rs[i].y + R};
		for(int k=0; k<2; k++) {
			auto it = Ys.lower_bound(pi(co[k] - R, -1) );
			if(it == Ys.end()) continue;
			int y = it->one, jx = it->two;
			if(y <= co[k]) {
				Ed[ix].push_back(jx);
				Ed[jx].push_back(ix);
//				printf("push %d %d\n", ix, jx);
			}
		}
	}
}
int main() {
	cin >> N >> R;
	int st = -1;
	REP(i, N) {
		int x, y; scanf("%d%d", &x, &y);
		Rs.push_back(RT(x, y, i));
		if(x+y == 0) st = i;
		S[i] = x+y+2*R;
	}
	cin >> K;

	for(int k=0; k<2; k++) {
		sort(ALL(Rs), sortX);
		makeGraph();
		for(RT &e : Rs) swap(e.x, e.y);
	}

	vector<bool> vis(N, false);
	queue<int> Q; Q.push(st);  vis[st] = true;
	int ans = 0;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		ans = max(ans, S[v]);
		for(int w : Ed[v]) {
			if(vis[w]) continue; vis[w] = true;
			Q.push(w);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

frog.cpp: In function 'int main()':
frog.cpp:61:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

Subtask #1
1.98 / 1.98

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4764 KB Output is correct
2 Correct 0 ms 4764 KB Output is correct
3 Correct 0 ms 4764 KB Output is correct
4 Correct 0 ms 4764 KB Output is correct
5 Correct 0 ms 4764 KB Output is correct
6 Correct 0 ms 4764 KB Output is correct
7 Correct 0 ms 4764 KB Output is correct

Subtask #2
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4764 KB Output is correct
2 Correct 3 ms 4764 KB Output is correct
3 Correct 0 ms 4764 KB Output is correct
4 Correct 3 ms 4764 KB Output is correct
5 Correct 0 ms 4764 KB Output is correct
6 Correct 3 ms 4764 KB Output is correct
7 Correct 3 ms 4764 KB Output is correct

Subtask #3
3.52 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4764 KB Output is correct
2 Correct 0 ms 4764 KB Output is correct
3 Correct 0 ms 4764 KB Output is correct
4 Correct 0 ms 4764 KB Output is correct
5 Correct 3 ms 4764 KB Output is correct
6 Correct 0 ms 4764 KB Output is correct
7 Correct 3 ms 4936 KB Output is correct

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 9 ms 4936 KB Output is correct
4 Correct 3 ms 4936 KB Output is correct
5 Correct 6 ms 4936 KB Output is correct
6 Correct 13 ms 5332 KB Output is correct
7 Correct 13 ms 5068 KB Output is correct

Subtask #5
4.62 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 6 ms 4936 KB Output is correct
4 Correct 6 ms 5068 KB Output is correct
5 Correct 9 ms 5132 KB Output is correct
6 Correct 23 ms 5432 KB Output is correct
7 Correct 33 ms 5756 KB Output is correct

Subtask #6
5.06 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6548 KB Output is correct
2 Correct 69 ms 6404 KB Output is correct
3 Correct 166 ms 9044 KB Output is correct
4 Correct 69 ms 6008 KB Output is correct
5 Correct 63 ms 6272 KB Output is correct
6 Correct 206 ms 9840 KB Output is correct
7 Correct 163 ms 9048 KB Output is correct