QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128258#4996. Icy ItineraryHanx16MsgrWA 1ms5528kbC++141.1kb2023-07-20 19:41:222023-07-20 19:41:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-20 19:41:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5528kb
  • [2023-07-20 19:41:22]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i, x, y) for (int i = x, i##end = y; i <= iend; ++i)
using namespace std;
constexpr int _N = 3e5 + 5;
int n, m, pre[_N], nxt[_N];
unordered_set<long long> H;
void Ins(int x, int y) { H.insert(1ll * x * _N + y); }
bool Chk(int x, int y) { return H.count(1ll * x * _N + y); }
void Add(int x, int y, int i) { pre[y] = i, nxt[x] = i, pre[i] = x, nxt[i] = y; }
signed main() {
   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   cin >> n >> m;
   For(i, 1, n) {
      int x, y;
      cin >> x >> y, Ins(x, y), Ins(y, x);
   }
   int p = 2;
   pre[0] = 2, pre[1] = 0, pre[2] = 1;
   nxt[0] = 1, nxt[1] = 2, nxt[2] = 0;
   For(i, 3, n) if (p == 1) {
      p = pre[0]; Add(p, nxt[p], i);
      if (Chk(p, pre[p]) == Chk(p, nxt[p])) p = 1;
   } else if (Chk(p, i) == Chk(p, pre[p])) {
      Add(p, nxt[p], i);
      if (nxt[i] && Chk(i, pre[i]) == Chk(i, nxt[i])) p = nxt[i];
      else p = i;
   } else {
      Add(pre[p], p, i);
      if (pre[i] && Chk(i, pre[i]) == Chk(i, nxt[i])) p = pre[i];
      else p = i;
   }
   for (int i = nxt[0]; i; i = nxt[i]) cout << i << ' ';
   cout << '\n';
}

详细

Test #1:

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

input:

4 4
1 2
1 3
1 4
3 4

output:

1 3 4 2 

result:

ok qwq

Test #2:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

5 0

output:

1 2 3 4 5 

result:

ok qwq

Test #3:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

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

output:

1 3 4 5 6 2 8 9 10 7 

result:

ok qwq

Test #4:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

2 1
1 2

output:

1 2 

result:

ok qwq

Test #5:

score: 0
Accepted
time: 1ms
memory: 5528kb

input:

2 0

output:

1 2 

result:

ok qwq

Test #6:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

3 1
1 3

output:

1 2 3 

result:

ok qwq

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 5500kb

input:

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

output:

1 2 5 6 7 8 10 9 4 3 

result:

wrong answer Changed color too many times (4)