QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714039#8056. Travel 2frankly6TL 1ms3720kbC++171.1kb2024-11-05 21:21:402024-11-05 21:21:41

Judging History

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

  • [2024-11-05 21:21:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3720kb
  • [2024-11-05 21:21:40]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cstring>
#include<unordered_map>
using namespace std;
const int MX=2550;

int T;
int start, num, now;
void ask(int e)
{
    cout << "> " << e << '\n';
    cout.flush();
    cin >> now >> num;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> T;
    while(T--)
    {
        vector<unordered_map<int,int>> G(MX);
        vector<int> fa(MX), id(MX);
        cin >> start >> num; now=start;
        while(now!=start||id[now]!=num)
        {
            if(id[now]==num) {ask(G[now][fa[now]]); continue;} //finish subtree & return to father
            int pre=now;
            ask(++id[now]); //try to expand
            G[pre][now]=id[pre]; //pre's try num
            if(now==fa[pre]) ask(G[now][pre]); //KEY edge, return to son
            else if(!fa[now]) fa[now]=pre; //upd KEY edge
        }
        cout << "! ";
        for(int u=1;u<MX;u++)
            for(auto [v,id]:G[u])
                if(u<v) cout << u << " " << v << " ";
        cout << '\n'; cout.flush();
        string s; cin >> s;
    }
    return (0-0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
1 3
Correct

output:

> 1
> 1
> 1
> 1
! 1 2 
> 1
> 1
> 1
> 2
> 1
> 2
> 1
> 2
> 1
> 3
> 1
! 1 4 1 3 1 2 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
1 9
4 9
1 9
4 9
3 9
4 9
7 7
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
4 9
7 7
8 8
5 8
8 8
10 6
2 7
10 6
8 8
9 8
1 9
8 8
7 7
5 8
9 8
3 9
9 8
5 8
2 7
6 9
10 6
4 9
10 6
6 9
5 8
3 9
2 7
3 9
5 8
6 9
8 8
3 9
10 6
3 9
8 8
6 9
3 9
7 7
3 9
6 9
9 8
2 7
5 8
7 7
9 8
8...

output:

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

result: