QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#520870	#8650. Island Hopping	green_gold_dog^#	65	8ms	4192kb	C++20	1.2kb	2024-08-15 16:54:32	2024-08-15 16:54:32

Judging History

你现在查看的是最新测评结果

[2024-08-15 16:54:32]
评测

测评结果：65
用时：8ms
内存：4192kb

查看

[2024-08-15 16:54:32]
提交

answer

#include "island.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

map<pair<ll, ll>, ll> mind;

ll get(ll x, ll y) {
	if (mind.find(make_pair(x, y)) != mind.end()) {
		return mind[make_pair(x, y)];
	}
	return mind[make_pair(x, y)] = query(x + 1, y + 1) - 1;
}

void ans(ll x, ll y) {
	answer(x + 1, y + 1);
}

struct DSU {
	vector<ll> p;
	DSU(ll n) {
		p.resize(n);
		for (ll i = 0; i < n; i++) {
			p[i] = i;
		}
	}
	ll get(ll v) {
		return (v == p[v] ? v : p[v] = get(p[v]));
	}
	bool unite(ll a, ll b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return false;
		}
		p[a] = b;
		return true;
	}
};

void solve(ll n, ll l) {
	vector<vector<ll>> to(n);
	vector<ll> col(n, 0);
	ll ost = n - 1;
	DSU d(n);
	for (ll i = 0; i < n; i++) {
		ll start = 0;
		for (auto j : to[i]) {
			if (j < i) {
				start++;
			}
		}
		while (start < n - 1 && ost > 0) {
			ll x = get(i, start);
			if (d.get(x) == d.get(i)) {
				break;
			}
			if (x < i) {
				break;
			}
			if (get(x, col[x]) == i) {
				col[x]++;
				ost--;
				to[i].push_back(x);
				to[x].push_back(i);
				d.unite(x, i);
			} else {
				break;
			}
			start++;
		}
	}
	for (ll i = 0; i < n; i++) {
		for (auto j : to[i]) {
			if (j > i) {
				ans(i, j);
			}
		}
	}
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 1ms

memory: 3884kb

input:

output:

result:

ok

Test #2:

score: 2

Accepted

time: 1ms

memory: 4108kb

input:

output:

result:

ok

Test #3:

score: 2

Accepted

time: 1ms

memory: 4104kb

input:

output:

result:

ok

Subtask #2:

score: 4

Accepted

Test #4:

score: 4

Accepted

time: 7ms

memory: 3892kb

input:

output:

result:

ok

Test #5:

score: 4

Accepted

time: 0ms

memory: 3968kb

input:

output:

result:

ok

Test #6:

score: 4

Accepted

time: 0ms

memory: 3868kb

input:

output:

result:

ok

Test #7:

score: 4

Accepted

time: 0ms

memory: 3956kb

input:

output:

result:

ok

Test #8:

score: 4

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok

Subtask #3:

score: 0

Wrong Answer

Test #9:

score: 0

Wrong Answer

time: 2ms

memory: 3884kb

input:

output:

result:

wrong answer Wrong Answer [3]

Subtask #4:

score: 9

Accepted

Test #15:

score: 9

Accepted

time: 0ms

memory: 4188kb

input:

output:

result:

ok

Test #16:

score: 9

Accepted

time: 3ms

memory: 3928kb

input:

output:

result:

ok

Test #17:

score: 9

Accepted

time: 0ms

memory: 3900kb

input:

output:

result:

ok

Test #18:

score: 9

Accepted

time: 7ms

memory: 3912kb

input:

output:

result:

ok

Test #19:

score: 9

Accepted

time: 2ms

memory: 3972kb

input:

output:

result:

ok

Test #20:

score: 9

Accepted

time: 0ms

memory: 3972kb

input:

output:

result:

ok

Test #21:

score: 9

Accepted

time: 0ms

memory: 4184kb

input:

output:

result:

ok

Test #22:

score: 9

Accepted

time: 0ms

memory: 4192kb

input:

output:

result:

ok

Subtask #5:

score: 13

Accepted

Test #23:

score: 13

Accepted

time: 3ms

memory: 3892kb

input:

output:

result:

ok

Test #24:

score: 13

Accepted

time: 0ms

memory: 3884kb

input:

output:

result:

ok

Test #25:

score: 13

Accepted

time: 2ms

memory: 3956kb

input:

output:

result:

ok

Test #26:

score: 13

Accepted

time: 2ms

memory: 3908kb

input:

output:

result:

ok

Test #27:

score: 13

Accepted

time: 0ms

memory: 3900kb

input:

output:

result:

ok

Test #28:

score: 13

Accepted

time: 0ms

memory: 3888kb

input:

output:

result:

ok

Test #29:

score: 13

Accepted

time: 5ms

memory: 3976kb

input:

output:

result:

ok

Test #30:

score: 13

Accepted

time: 2ms

memory: 3928kb

input:

output:

result:

ok

Test #31:

score: 13

Accepted

time: 0ms

memory: 4184kb

input:

output:

result:

ok

Subtask #6:

score: 15

Accepted

Test #32:

score: 15

Accepted

time: 0ms

memory: 4180kb

input:

output:

result:

ok

Test #33:

score: 15

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok

Test #34:

score: 15

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok

Test #35:

score: 15

Accepted

time: 5ms

memory: 3892kb

input:

output:

result:

ok

Test #36:

score: 15

Accepted

time: 3ms

memory: 3888kb

input:

output:

result:

ok

Test #37:

score: 15

Accepted

time: 7ms

memory: 3860kb

input:

output:

result:

ok

Test #38:

score: 15

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok

Test #39:

score: 15

Accepted

time: 0ms

memory: 4188kb

input:

output:

result:

ok

Test #40:

score: 15

Accepted

time: 7ms

memory: 3924kb

input:

output:

result:

ok

Test #41:

score: 15

Accepted

time: 2ms

memory: 3892kb

input:

output:

result:

ok

Test #42:

score: 15

Accepted

time: 7ms

memory: 4184kb

input:

output:

result:

ok

Test #43:

score: 15

Accepted

time: 0ms

memory: 4184kb

input:

output:

result:

ok

Test #44:

score: 15

Accepted

time: 4ms

memory: 3976kb

input:

output:

result:

ok

Test #45:

score: 15

Accepted

time: 0ms

memory: 4188kb

input:

output:

result:

ok

Test #46:

score: 15

Accepted

time: 0ms

memory: 3868kb

input:

output:

result:

ok

Test #47:

score: 15

Accepted

time: 3ms

memory: 4152kb

input:

output:

result:

ok

Test #48:

score: 15

Accepted

time: 4ms

memory: 4156kb

input:

output:

result:

ok

Test #49:

score: 15

Accepted

time: 7ms

memory: 3788kb

input:

output:

result:

ok

Test #50:

score: 15

Accepted

time: 2ms

memory: 3888kb

input:

output:

result:

ok

Test #51:

score: 15

Accepted

time: 0ms

memory: 3884kb

input:

output:

result:

ok

Test #52:

score: 15

Accepted

time: 7ms

memory: 3896kb

input:

output:

result:

ok

Test #53:

score: 15

Accepted

time: 3ms

memory: 3956kb

input:

output:

result:

ok

Test #54:

score: 15

Accepted

time: 4ms

memory: 3912kb

input:

output:

result:

ok

Test #55:

score: 15

Accepted

time: 5ms

memory: 4184kb

input:

output:

result:

ok

Test #56:

score: 15

Accepted

time: 0ms

memory: 4088kb

input:

output:

result:

ok

Test #57:

score: 15

Accepted

time: 0ms

memory: 4124kb

input:

output:

result:

ok

Subtask #7:

score: 22

Accepted

Test #58:

score: 22

Accepted

time: 3ms

memory: 3896kb

input:

output:

result:

ok

Test #59:

score: 22

Accepted

time: 0ms

memory: 3976kb

input:

output:

result:

ok

Test #60:

score: 22

Accepted

time: 0ms

memory: 3976kb

input:

output:

result:

ok

Test #61:

score: 22

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok

Test #62:

score: 22

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok

Test #63:

score: 22

Accepted

time: 2ms

memory: 4188kb

input:

output:

result:

ok

Test #64:

score: 22

Accepted

time: 0ms

memory: 4160kb

input:

output:

result:

ok

Test #65:

score: 22

Accepted

time: 4ms

memory: 3896kb

input:

output:

result:

ok

Test #66:

score: 22

Accepted

time: 7ms

memory: 3956kb

input:

output:

result:

ok

Test #67:

score: 22

Accepted

time: 1ms

memory: 3884kb

input:

output:

result:

ok

Test #68:

score: 22

Accepted

time: 3ms

memory: 3908kb

input:

output:

result:

ok

Test #69:

score: 22

Accepted

time: 4ms

memory: 3908kb

input:

output:

result:

ok

Test #70:

score: 22

Accepted

time: 2ms

memory: 4136kb

input:

output:

result:

ok

Test #71:

score: 22

Accepted

time: 7ms

memory: 3844kb

input:

output:

result:

ok

Test #72:

score: 22

Accepted

time: 0ms

memory: 3928kb

input:

output:

result:

ok

Test #73:

score: 22

Accepted

time: 5ms

memory: 3900kb

input:

output:

result:

ok

Test #74:

score: 22

Accepted

time: 0ms

memory: 3932kb

input:

output:

result:

ok

Test #75:

score: 22

Accepted

time: 2ms

memory: 4188kb

input:

output:

result:

ok

Test #76:

score: 22

Accepted

time: 3ms

memory: 3904kb

input:

output:

result:

ok

Test #77:

score: 22

Accepted

time: 4ms

memory: 3956kb

input:

output:

result:

ok

Test #78:

score: 22

Accepted

time: 0ms

memory: 3928kb

input:

output:

result:

ok

Test #79:

score: 22

Accepted

time: 0ms

memory: 3900kb

input:

output:

result:

ok

Test #80:

score: 22

Accepted

time: 0ms

memory: 4192kb

input:

output:

result:

ok

Test #81:

score: 22

Accepted

time: 0ms

memory: 3884kb

input:

output:

result:

ok

Test #82:

score: 22

Accepted

time: 5ms

memory: 3892kb

input:

output:

result:

ok

Test #83:

score: 22

Accepted

time: 8ms

memory: 3892kb

input:

output:

result:

ok

Subtask #8:

score: 0

Wrong Answer

Test #84:

score: 0

Wrong Answer

time: 2ms

memory: 4164kb

input:

output:

result:

wrong answer Wrong Answer [3]