QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771082#7866. TeleportationgzyTL 3ms16900kbC++141.4kb2024-11-22 09:37:362024-11-22 09:37:36

Judging History

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

  • [2024-11-22 09:37:36]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:16900kb
  • [2024-11-22 09:37:36]
  • 提交

answer

#include<bits/stdc++.h>
#define pb emplace_back
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
using ll = long long;
using db = double;

constexpr int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() getchar()//(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? EOF : *p1++)

int rd() {int x = 0, f = 1;char c = gc();while (!isdigit(c)) {if (c == '-') f = -1;c = gc();}while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();return x * f;}

const int N = 2e5 + 7;
int i, j, k, n, m;
int f[N], a[N], v[N], u[N];
set<int> d[N];
queue<int> q, t;

int dis(int x, int y) {return y - x + (x > y) * n;}

signed main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	n = rd(), k = rd();
	for(i = 0; i < n; i++) v[i] = ((a[i] = rd()) + i) % n;
	for(i = 0; i < n; i++) if(i != k) d[v[i]].insert(i);
	q.push(k), t.push(k);
	for(int x : d[k]) {
		if(a[x]) q.push(x), t.push(x);
	}
	d[k].clear();
	while(q.size()) {
		k = q.front(), q.pop();
		i = t.front(), t.pop();
		while(!d[i].size()) {
			i = (i - 1 + n) % n;
			if(u[i]) break;
		}
		if(u[i]) continue;
		u[k] = 1;
		for(int x : d[i]) {
			f[x] = f[k] + dis(i, k) + 1;
			if(a[x]) q.push(x), t.push(x);
		}
		q.push(k), t.push(i);
		d[i].clear();
	}
	printf("%d\n", f[0]);
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16736kb

input:

4 3
0 1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2ms
memory: 16900kb

input:

4 3
0 0 0 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 0ms
memory: 16468kb

input:

4 3
2 2 2 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 3ms
memory: 16872kb

input:

2 1
0 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: -100
Time Limit Exceeded

input:

2 1
1 1

output:


result: