QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376903#8056. Travel 2PetroTarnavskyi#AC ✓178ms5080kbC++201.9kb2024-04-04 18:33:292024-04-04 18:33:29

Judging History

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

  • [2024-04-04 18:33:29]
  • 评测
  • 测评结果:AC
  • 用时:178ms
  • 内存:5080kb
  • [2024-04-04 18:33:29]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 2'747;
set<int> g[N];
int sz[N];
VI G[N];
int ptr[N];
int p[N];
int pm[N];
bool used[N];
bool inMst[N];
int n = 0;

PII query(int idx)
{
	cout << "> " << idx + 1 << endl;
	int v, d;
	cin >> v >> d;
	n = max(n, v);
	v--;
	return {v, d};
}

void dfs(int v, int t)
{
	//cerr << v << ' ' << par << ' ' << ptr[v] << ' ' << sz[v] << ' ' << SZ(G[v]) << ' ' << p[v] << '\n';

	int cur = v;
	while (ptr[v] < sz[v] || cur != v)
	{
		auto [to, sto] = query(ptr[v]);
		g[v].insert(to);
		sz[to] = sto;
		if (!inMst[to])
		{
			inMst[to] = true;
			G[v].PB(ptr[v]);
			pm[to] = v;
		}
		if (pm[v] == to)
			p[v] = ptr[v];
		ptr[v]++;
		v = to;
	}	
	if (used[v])
	{
		if (p[v] == -1 || t == 0)
			return;
		query(p[v]);
		return;
	}
	used[v] = true;
	for (auto idx : G[v])
	{
		auto [to, sto] = query(idx);
		dfs(to, 1);
	}
	if (p[v] == -1 || t == 0)
		return;
	query(p[v]);
}

void solve()
{
	FOR (i, 0, N)
	{
		g[i].clear();
		G[i].clear();
		p[i] = -1;
		used[i] = false;
		inMst[i] = false;
		sz[i] = 0;
		ptr[i] = 0;
		pm[i] = -1;
	}
	n = 0;
	int v, d;
	cin >> v >> d;
	n = max(n, v);
	v--;
	sz[v] = d;
	inMst[v] = true;
	dfs(v, 0);
	cout << "!";
	FOR (i, 0, n)
	{
		for (auto to : g[i])
			if (to < i)
				cout << ' ' << i + 1 << ' ' << to + 1;
	}
	cout << endl;
	string s;
	cin >> s;
	assert(s == "Correct");
}

int main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3756kb

input:

2
1 1
2 1
1 1
2 1
1 1
Correct
1 3
2 2
1 3
3 1
1 3
4 2
1 3
2 2
4 2
2 2
1 3
3 1
1 3
4 2
1 3
Correct

output:

> 1
> 1
> 1
> 1
! 2 1
> 1
> 1
> 2
> 1
> 3
> 1
> 1
> 2
> 2
> 1
> 2
> 1
> 3
> 1
! 2 1 3 1 4 1 4 2

result:

ok correct

Test #2:

score: 0
Accepted
time: 169ms
memory: 3700kb

input:

1000
1 9
2 7
1 9
3 9
1 9
4 9
1 9
5 8
1 9
6 9
1 9
7 7
1 9
8 8
1 9
9 8
1 9
10 6
1 9
2 7
3 9
4 9
3 9
9 8
3 9
2 7
10 6
2 7
6 9
2 7
5 8
8 8
5 8
9 8
5 8
2 7
9 8
2 7
4 9
7 7
4 9
10 6
8 8
10 6
4 9
8 8
9 8
8 8
7 7
8 8
3 9
5 8
3 9
10 6
6 9
10 6
3 9
8 8
6 9
5 8
6 9
8 8
4 9
5 8
7 7
5 8
4 9
2 7
1 9
3 9
7 7
3 9
6...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 1
> 2
> 2
> 2
> 3
> 2
> 4
> 3
> 2
> 4
> 2
> 5
> 2
> 2
> 3
> 3
> 4
> 6
> 4
> 7
> 3
> 2
> 4
> 3
> 3
> 4
> 5
> 4
> 5
> 5
> 3
> 6
> 5
> 5
> 6
> 5
> 3
> 6
> 7
> 7
> 4
> 6
> 5
> 8
> 6
> 7
> 4
> 8
> 7
> 1
> 2
> 8
> 5
> 9
> 6
> 1
> 3
...

result:

ok correct

Test #3:

score: 0
Accepted
time: 149ms
memory: 3996kb

input:

500
1 19
2 8
1 19
3 7
1 19
4 8
1 19
5 7
1 19
6 7
1 19
7 11
1 19
8 4
1 19
9 7
1 19
10 9
1 19
11 8
1 19
12 7
1 19
13 4
1 19
14 9
1 19
15 8
1 19
16 7
1 19
17 10
1 19
18 7
1 19
19 7
1 19
20 6
1 19
2 8
17 10
2 8
3 7
20 6
3 7
11 8
3 7
4 8
3 7
2 8
14 9
19 7
14 9
17 10
6 7
5 7
7 11
5 7
6 7
17 10
14 9
6 7
11...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 1
> 2
> 2
> 3
> 2
> 2
> 3
> 2
> 4
> 2
> 5
> 4
> 2
> 2
> 3
> 3
> 2
> 2
> 2
> 3
> 3
> 4
> 4
> 4
> 3
> 2
> 4
> 2
> 2
> 3
> 5
> 3
> 2
> 4
> ...

result:

ok correct

Test #4:

score: 0
Accepted
time: 134ms
memory: 3740kb

input:

100
1 99
2 5
1 99
3 5
1 99
4 10
1 99
5 3
1 99
6 9
1 99
7 6
1 99
8 8
1 99
9 9
1 99
10 5
1 99
11 4
1 99
12 7
1 99
13 6
1 99
14 8
1 99
15 7
1 99
16 7
1 99
17 7
1 99
18 6
1 99
19 10
1 99
20 4
1 99
21 4
1 99
22 5
1 99
23 6
1 99
24 10
1 99
25 4
1 99
26 10
1 99
27 7
1 99
28 6
1 99
29 11
1 99
30 5
1 99
31 7...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #5:

score: 0
Accepted
time: 178ms
memory: 4284kb

input:

10
1 999
2 8
1 999
3 9
1 999
4 8
1 999
5 7
1 999
6 7
1 999
7 4
1 999
8 4
1 999
9 13
1 999
10 11
1 999
11 7
1 999
12 7
1 999
13 5
1 999
14 5
1 999
15 8
1 999
16 9
1 999
17 5
1 999
18 5
1 999
19 8
1 999
20 4
1 999
21 8
1 999
22 8
1 999
23 6
1 999
24 8
1 999
25 2
1 999
26 9
1 999
27 5
1 999
28 6
1 999
...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #6:

score: 0
Accepted
time: 146ms
memory: 4696kb

input:

4
1 999
2 24
1 999
3 20
1 999
4 17
1 999
5 29
1 999
6 21
1 999
7 21
1 999
8 19
1 999
9 21
1 999
10 14
1 999
11 12
1 999
12 17
1 999
13 23
1 999
14 23
1 999
15 16
1 999
16 14
1 999
17 16
1 999
18 15
1 999
19 16
1 999
20 19
1 999
21 16
1 999
22 16
1 999
23 25
1 999
24 23
1 999
25 22
1 999
26 16
1 999
...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #7:

score: 0
Accepted
time: 133ms
memory: 4964kb

input:

4
1 199
2 106
1 199
3 95
1 199
4 102
1 199
5 103
1 199
6 103
1 199
7 110
1 199
8 109
1 199
9 104
1 199
10 98
1 199
11 85
1 199
12 94
1 199
13 86
1 199
14 105
1 199
15 102
1 199
16 96
1 199
17 97
1 199
18 94
1 199
19 112
1 199
20 108
1 199
21 116
1 199
22 109
1 199
23 104
1 199
24 96
1 199
25 92
1 19...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #8:

score: 0
Accepted
time: 89ms
memory: 5080kb

input:

4
1 140
2 140
1 140
3 140
1 140
4 140
1 140
5 140
1 140
6 140
1 140
7 140
1 140
8 140
1 140
9 140
1 140
10 140
1 140
11 140
1 140
12 140
1 140
13 140
1 140
14 140
1 140
15 140
1 140
16 140
1 140
17 140
1 140
18 140
1 140
19 140
1 140
20 140
1 140
21 140
1 140
22 140
1 140
23 140
1 140
24 140
1 140
2...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Test #9:

score: 0
Accepted
time: 98ms
memory: 4384kb

input:

4
1 2498
2 2
1 2498
3 2
1 2498
4 2
1 2498
5 2
1 2498
6 2
1 2498
7 2
1 2498
8 2
1 2498
9 2
1 2498
10 2
1 2498
11 2
1 2498
12 2
1 2498
13 2
1 2498
14 2
1 2498
15 2
1 2498
16 2
1 2498
17 2
1 2498
18 2
1 2498
19 2
1 2498
20 2
1 2498
21 2
1 2498
22 2
1 2498
23 2
1 2498
24 2
1 2498
25 2
1 2498
26 2
1 2498...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 10
> 1
> 11
> 1
> 12
> 1
> 13
> 1
> 14
> 1
> 15
> 1
> 16
> 1
> 17
> 1
> 18
> 1
> 19
> 1
> 20
> 1
> 21
> 1
> 22
> 1
> 23
> 1
> 24
> 1
> 25
> 1
> 26
> 1
> 27
> 1
> 28
> 1
> 29
> 1
> 30
> 1
> 31
> 1
> 32
> 1
> 33
> 1
> 34
> 1
> 3...

result:

ok correct

Extra Test:

score: 0
Extra Test Passed