QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#342314	#4087. 철도	tuanlinh123	0	6ms	4372kb	C++20	1.5kb	2024-03-01 10:32:30	2024-03-01 10:32:31

Judging History

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

[2024-03-01 10:32:31]
评测

测评结果：0
用时：6ms
内存：4372kb

查看

[2024-03-01 10:32:30]
提交

answer

#include "railroad.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

vector <pll> encode_map(ll n, ll k, ll &x, vector <pll> e) 
{
    vector <vector <bool>> check(n+1, vector <bool>(n+1, 0));
    vector <vector <ll>> A(n+1);
    for (pll i:e) A[i.fi].pb(i.se), A[i.se].pb(i.fi), check[i.fi][i.se]=check[i.se][i.fi]=1;
    pll Max={0, 0};
    for (ll i=1; i<=n; i++)
        Max=max(Max, {A[i].size(), i});
    x=Max.se;
    vector <ll> dep(n+1, -1);
    queue <ll> q; dep[x]=0, q.push(x);
    while (!q.empty())
    {
        ll u=q.front(); q.pop();
        for (ll v:A[u])
            if (dep[v]==-1)
                dep[v]=dep[u]+1, q.push(v);
    }
    vector <pll> ans;
    ll cnt=0;
    for (ll i=1; i<=n; i++)
        for (ll j=i+1; j<=n; j++)
            if (cnt<k && !check[i][j]) ans.pb({i, j}), cnt++;
    assert(ans.size()==k);
    return ans;
}

vector <pll> decode_map(ll n, ll k, ll x, vector <pll> e) 
{
	vector <vector <ll>> A(n+1);
    for (pll i:e) A[i.fi].pb(i.se), A[i.se].pb(i.fi);
    vector <ll> dep(n+1, -1);
    queue <ll> q; q.push(x), dep[x]=0;
    while (!q.empty())
    {
        ll u=q.front(); q.pop();
        for (ll v:A[u])
            if (dep[v]==-1)
                dep[v]=dep[u]+1, q.push(v);
    }
    vector <pll> ans;
    for (pll i:e)
        if (dep[i.fi]==dep[i.se])
            ans.pb(i);
    return ans;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 3868kb

input:

jlsvaji35cwcxva-INPUT-gwl9ravworar2t1
200
4 1
2 3
3 1
4 1
4 1
1 4
3 1
2 1
4 1
4 3
1 3
2 1
3 1
2 1
3 1
4 1
1 4
4 3
2 3
4 1
3 1
1 4
2 1
3 1
1 3
2 1
4 1
2 4
1 2
3 4
4 1
2 3
1 3
4 1
4 1
3 1
1 4
2 3
4 1
3 2
1 4
4 2
3 1
3 1
2 3
4 1
2 4
1 4
4 3
3 1
3 1
2 1
3 1
1 3
2 3
4 1
2 4
4 1
3 1
4 1
2 4
1 4
3 1
3 1
2 ...

output:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
200
4 1 3
1 4
2 3
3 1
2 1
4 1 1
1 2
4 1
3 1
3 2
4 1 3
2 1
4 3
1 4
1 3
3 1 1
3 2
3 1
1 2
4 1 4
2 1
3 2
4 3
4 1
4 1 1
1 4
1 3
2 3
1 2
3 1 1
3 2
1 2
3 1
4 1 4
3 4
2 1
2 4
3 1
4 1 3
4 1
3 1
3 2
1 2
4 1 3
2 1
2 3
3 1
4 1
4 1 4
3 2
1 2
1 4
2 4
3 1 3
3 1
2 1
3 2
4 1 ...

input:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
200
4 1 3
1 4
2 3
3 1
2 1
4 1 1
1 2
4 1
3 1
3 2
4 1 3
2 1
4 3
1 4
1 3
3 1 1
3 2
3 1
1 2
4 1 4
2 1
3 2
4 3
4 1
4 1 1
1 4
1 3
2 3
1 2
3 1 1
3 2
1 2
3 1
4 1 4
3 4
2 1
2 4
3 1
4 1 3
4 1
3 1
3 2
1 2
4 1 3
2 1
2 3
3 1
4 1
4 1 4
3 2
1 2
1 4
2 4
3 1 3
3 1
2 1
3 2
4 1 ...

output:

wji3t9iql4gwq1n-OUTPUT-s6f20p5z2lkxbj3
WA
invalid edge count - decode

result:

wrong answer WA in grader: invalid edge count - decode

Subtask #2:

score: 0

Skipped

Subtask #3:

score: 0

Wrong Answer

Test #37:

score: 0

Wrong Answer

time: 6ms

memory: 4372kb

input:

jlsvaji35cwcxva-INPUT-gwl9ravworar2t1
196
24 11
13 17
4 8
22 19
15 13
10 14
6 10
9 6
23 1
1 15
5 9
12 23
16 21
8 5
11 24
2 22
21 11
18 3
3 20
20 12
17 7
19 18
24 2
14 16
22 10
16 11
3 15
6 5
17 19
15 17
11 18
20 10
8 1
14 22
4 3
22 8
2 21
12 14
1 9
19 12
7 4
10 13
18 7
21 16
5 2
13 6
42 6
11 24
14 3...

output:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
196
24 11 24
1 5
1 7
14 16
6 1
2 1
22 19
1 12
23 1
21 16
8 1
2 24
6 9
7 17
9 5
1 11
13 15
4 8
1 15
23 12
24 11
18 19
17 13
1 3
10 6
10 1
8 5
12 20
3 20
21 11
9 1
14 10
22 2
4 1
18 3
22 10 22
10 13
22 14
1 9
14 12
1 13
15 17
13 6
1 8
1 12
1 7
12 19
7 4
2 21
16 ...

input:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
196
24 11 24
1 5
1 7
14 16
6 1
2 1
22 19
1 12
23 1
21 16
8 1
2 24
6 9
7 17
9 5
1 11
13 15
4 8
1 15
23 12
24 11
18 19
17 13
1 3
10 6
10 1
8 5
12 20
3 20
21 11
9 1
14 10
22 2
4 1
18 3
22 10 22
10 13
22 14
1 9
14 12
1 13
15 17
13 6
1 8
1 12
1 7
12 19
7 4
2 21
16 ...

output:

wji3t9iql4gwq1n-OUTPUT-s6f20p5z2lkxbj3
WA
invalid edge count - decode

result:

wrong answer WA in grader: invalid edge count - decode

Subtask #4:

score: 0

Wrong Answer

Test #72:

score: 0

Wrong Answer

time: 6ms

memory: 4280kb

input:

jlsvaji35cwcxva-INPUT-gwl9ravworar2t1
196
146 27
27 45
119 45
4 45
61 45
1 45
115 45
51 45
16 45
134 45
83 45
64 45
86 45
7 45
62 45
78 45
46 17
128 45
30 17
41 45
14 45
12 45
52 45
32 45
139 45
96 45
84 45
116 17
11 45
72 131
42 45
105 45
106 45
130 45
125 45
127 45
112 45
22 45
100 17
70 17
43 45
...

output:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
196
146 27 45
45 52
112 45
43 45
47 45
45 50
45 41
24 1
45 48
68 45
28 45
45 133
45 78
45 83
135 45
25 45
45 8
45 22
45 109
20 1
59 45
1 16
15 45
86 45
66 45
45 76
45 113
1 14
10 45
17 116
10 1
45 82
18 1
45 87
1 19
131 35
45 55
45 115
77 45
26 1
17 39
131 71
...

input:

xesbjgyk879wak7-PIPE-o4pbvexzrdpcje2
OK
196
146 27 45
45 52
112 45
43 45
47 45
45 50
45 41
24 1
45 48
68 45
28 45
45 133
45 78
45 83
135 45
25 45
45 8
45 22
45 109
20 1
59 45
1 16
15 45
86 45
66 45
45 76
45 113
1 14
10 45
17 116
10 1
45 82
18 1
45 87
1 19
131 35
45 55
45 115
77 45
26 1
17 39
131 71
...

output:

wji3t9iql4gwq1n-OUTPUT-s6f20p5z2lkxbj3
WA
invalid edge count - decode

result:

wrong answer WA in grader: invalid edge count - decode

Subtask #5:

score: 0

Skipped