Submission #26009

#	Time	Username	Problem	Language	Result	Execution time	Memory
26009		kajebiii	개구리 (KOI13_frog)	C++14	0 / 22	56 ms	6548 KiB

frog

#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);
			}
		}
	}
}
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 == i) 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 (stderr)

frog.cpp: In function 'int main()':
frog.cpp:60: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: 0 / 1.98
• Subtask 2: 0 / 2.64
• Subtask 3: 0 / 3.52
• Subtask 4: 0 / 4.18
• Subtask 5: 0 / 4.62
• Subtask 6: 0 / 5.06