QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414916#8056. Travel 2kevinshan#AC ✓141ms5360kbC++172.5kb2024-05-20 02:13:012024-05-20 02:13:01

Judging History

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

  • [2024-05-20 02:13:01]
  • 评测
  • 测评结果:AC
  • 用时:141ms
  • 内存:5360kb
  • [2024-05-20 02:13:01]
  • 提交

answer

#pragma GCC optimize("Ofast,O3,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ps push
#define in insert
#define f first
#define s second
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";
#define cbit(x) __builtin_popcount(x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a*b/gcd(a, b))
const int xm[4] = {-1, 1, 0, 0};
const int ym[4] = {0, 0, -1, 1};
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 5;
const ll POW = 9973;

int deg[2505];
int par[2505];
vector<int> adj[2505];
int n;


// vector<int> test_g[20];
// int movecnt = 0;

void iterate(int x);
void dfs(int x) {
    // cout<<x<<" ";
    n = max(n, x);
    if(deg[x] > adj[x].size()){
        iterate(x);
        return;
    }
    int pdx;
    for(int i=1; i<=deg[x]; i++){
        if(adj[x][i-1] == par[x]) {
            pdx = i;
            continue;
        }
        if(par[adj[x][i-1]] != x) continue;
        cout<<"> "<<i<<endl;
        // movecnt++;

        int tx, tdx;
        cin>>tx>>tdx;


        // cout<<x<<"->"<<adj[x][i-1]<<endl;

        dfs(adj[x][i-1]);
    }
    if(par[x]) {
        // movecnt++;
        cout<<"> "<<pdx<<endl;
        // cout<<x<<":"<<pdx<<"|"; ca(adj[x]);
        // cout<<endl;
        // cout<<x<<"->"<<adj[x][pdx-1]<<endl;
        int tx, tdx;
        cin>>tx>>tdx;
    }
}
void iterate(int x) {
    // cout<<x<<" ";
    n = max(n, x);
    if(adj[x].size() == deg[x]) {
        dfs(x);
    }
    else {
        cout<<"> "<<adj[x].size() + 1<<endl;
        // movecnt++;
        int tx,tdx;
        cin>>tx>>tdx;

        // tx = test_g[x][adj[x].size()];
        // tdx = test_g[tx].size();


        deg[tx] = tdx;
        adj[x].pb(tx);
        if(adj[tx].size() == 0) par[tx] = x;
        iterate(tx);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){

        n = 1;
        int x;
        int dx;

        cin>>x>>dx;

        deg[x] = dx;
        
        iterate(1);


        cout<<"! ";
        for(int i=1; i<=n; i++) {
            for(int j:adj[i]) if(j>i) cout<<i<<" "<<j<<" ";
        }
        cout<<endl;
        string s; cin>>s;
        assert(s[0] == 'C');
        for(int i=1; i<=n; i++) {
            adj[i].clear();
            deg[i] = 0;
            par[i] = 0;
        }
        n = 1;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
! 1 2 
> 1
> 1
> 2
> 1
> 3
> 1
> 1
> 2
> 2
> 1
> 2
> 1
> 3
> 1
! 1 2 1 3 1 4 2 4 

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 119ms
memory: 3672kb

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! (1000 test cases)

Test #3:

score: 0
Accepted
time: 135ms
memory: 3824kb

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! (500 test cases)

Test #4:

score: 0
Accepted
time: 116ms
memory: 3756kb

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! (100 test cases)

Test #5:

score: 0
Accepted
time: 112ms
memory: 4296kb

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! (10 test cases)

Test #6:

score: 0
Accepted
time: 141ms
memory: 5316kb

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! (4 test cases)

Test #7:

score: 0
Accepted
time: 97ms
memory: 5360kb

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! (4 test cases)

Test #8:

score: 0
Accepted
time: 79ms
memory: 5196kb

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! (4 test cases)

Test #9:

score: 0
Accepted
time: 32ms
memory: 4504kb

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! (4 test cases)

Extra Test:

score: 0
Extra Test Passed