QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#679509#8056. Travel 2TokaiZaopen#TL 1ms3704kbC++202.8kb2024-10-26 17:45:472024-10-26 17:45:52

Judging History

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

  • [2024-10-26 17:45:52]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3704kb
  • [2024-10-26 17:45:47]
  • 提交

answer

#include <bits/stdc++.h>

#define int ll
using ll = long long;

// #define MING_LE

using namespace std;

map<int, int> mp[2510];
int num[2510];
int fa[2510];
bool vis[2510];
int cur[2510];

set<pair<int, int>> ans;

void dfs(int x, int f);
void solve();

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int __ = 1;
    cin >> __;

    while (__--)
        solve();

    return 0;
}

void solve()
{
    ans.clear();
    int n, m;
    for (int i = 1; i <= 2500; i++)
    {
        mp[i].clear();
        num[i] = -1;
        fa[i] = -1;
        vis[i] = 0;
        cur[i] = 1;
    }

    int x, p;
    cin >> x >> p;
    num[x] = p;
    fa[x] = 0;
    vis[x] = 1;
    int now = x;

    dfs(x, 0);
    cout << "!";
    for (auto it : ans)
        cout << " " << it.first << " " << it.second;
    cout << endl;

    string dyc3;
    cin >> dyc3;
}

void dfs(int x, int f)
{
    fa[x] = f;
    vis[x] = 1;
    int ret;
    for (int i = 1; i <= num[x]; i++)
    {
        if (mp[x].count(i) && mp[x][i] == f)
        {
            ret = i;
            continue;
        }
        if (mp[x].count(i) && vis[mp[x][i]])
            continue;

        cout << "> " << i << endl;
        int to, p;
        cin >> to >> p;
        num[to] = p;
        mp[x][i] = to;
        ans.emplace(min(to, x), max(to, x));

        if (to == f)
        {
            ret = i;
            for (int j = 1; j <= num[to]; j++)
            {
                if (mp[to][j] == x)
                {
                    cout << "> " << j << endl;
                    int dyc1, dyc2;
                    cin >> dyc1 >> dyc2;
                    break;
                }
            }
        }

        if (vis[to])
        {
            // int buffer;
            // for (int j = 1; j <= num[to]; j++)
            // {
            //     if (mp[to][j] == x)
            //     {
            //         buffer = j;
            //         break;
            //     }
            // }
            // int dyc1, dyc2;
            // cout << "> " << buffer << endl;
            // cin >> dyc1 >> dyc2;

            bool flag = 0;
            for (auto it : mp[to])
                if (it.second == x)
                {
                    flag = 1;
                    break;
                }
            if (!flag)
            {
                ans.emplace(min(to, x), max(to, x));
                dfs(to, fa[to]);
            }
            else
            {
                continue;
            }
        }
        else
        {
            dfs(to, x);
        }
    }

    if (x != 1)
    {
        int dyc1, dyc2;
        cout << "> " << ret << endl;
        cin >> dyc1 >> dyc2;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok correct! (2 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:

> 1
> 1
> 1
> 2
> 1
> 2
> 3
> 1
> 3
> 2
> 2
> 1
> 4
> 1
> 4
> 2
> 1
> 5
> 1
> 5
> 2
> 3
> 1
> 6
> 1
> 6
> 2
> 2
> 2
> 3
> 4
> 3
> 3
> 4
> 4
> 5
> 2
> 2
> 3
> 2
> 3
> 3
> 4
> 5
> 4
> 5
> 6
> 3
> 4
> 2
> 5
> 4
> 6
> 7
> 1
> 5
> 3
> 5
> 6
> 6
> 7

result: