QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#342324	#4087. 철도	tuanlinh123	0	6ms	4084kb	C++20	1.6kb	2024-03-01 10:39:49	2024-03-01 10:39:49

Judging History

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

[2024-03-01 10:39:49]
评测

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

查看

[2024-03-01 10:39:49]
提交

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] && dep[i]==dep[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);
    assert(ans.size()==k);
    return ans;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 3812kb

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
3 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 2
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
3 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 2
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

Stage 1: Program answer Runtime Error

Test #37:

score: 0

Stage 1: Program answer Runtime Error

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:

input:

output:

result:

Subtask #4:

score: 0

Wrong Answer

Test #72:

score: 0

Wrong Answer

time: 6ms

memory: 4084kb

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
25 1
45 48
68 45
28 45
45 133
45 78
45 83
135 45
25 45
45 8
45 22
45 109
21 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
19 1
45 87
1 20
131 35
45 55
45 115
77 45
27 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
25 1
45 48
68 45
28 45
45 133
45 78
45 83
135 45
25 45
45 8
45 22
45 109
21 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
19 1
45 87
1 20
131 35
45 55
45 115
77 45
27 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