QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799162#3148. Train Faremodwwe12 2ms6724kbC++232.8kb2024-12-04 23:56:592024-12-04 23:57:00

Judging History

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

  • [2024-12-04 23:57:00]
  • 评测
  • 测评结果:12
  • 用时:2ms
  • 内存:6724kb
  • [2024-12-04 23:56:59]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 1e18;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    ll a;
    int  b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int el = 19;
main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo();
//   checktime
}
ib dp[100002];
vector<ib> v[100002];
int c[100002];
ib mer(ib a,ib b)
{
    if(a.a<b.a) return a;
    if(b.a<a.a) return b;
    return {a.a,max(a.b,b.b)};
}
void bfs()
{
    deque<int> p;
    p.pb(1);
    dp[1]= {0,k+1};
    for(int i=2; i<=n; i++)
        dp[i].a=inf,dp[i].b=k+1;
    while(!p.empty())
    {
        int x=p.front();
        p.pop_front();
        for(auto f:v[x])
            if(dp[f.a].a==inf)
            {
                dp[f.a].a=dp[x].a+1;
                dp[f.a].b=min(dp[x].b,c[f.b]);
                p.pb(f.a);
            }
            else
            {
                dp[f.a]=mer(dp[f.a], {dp[x].a+1,min(dp[x].b,c[f.b])});
            }
    }
    memset(c,0,sizeof c);
    for(int i=2; i<=n; i++)
    {
        c[dp[i].b]++;
    }
}
void phongbeo()
{
    cin>>n>>m>>k;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r;
        v[l].pb({r,i});
        v[r].pb({l,i});
        c[i]=k+1;
    }
    for(int i=1; i<=k; i++)
    {
        cin>>l;
        c[l]=i;
    }
    bfs();
    for(int i=1; i<=k; i++)
        c[i]+=c[i-1],cout<<c[i],down
    }

详细

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 1ms
memory: 6708kb

input:

100 99 30
98 22
47 21
49 48
95 82
33 62
71 43
35 44
48 37
91 65
22 48
69 75
33 22
60 58
2 35
59 23
19 94
45 81
58 55
72 77
20 70
97 92
29 21
47 27
93 61
13 78
25 73
54 83
40 87
67 26
48 32
5 38
22 68
63 64
39 37
14 33
2 51
73 15
90 14
61 98
94 33
17 22
34 73
1 55
18 21
68 4
95 94
50 100
13 52
48 87
...

output:

94
94
94
94
94
94
94
94
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95
95

result:

ok 30 lines

Test #2:

score: 12
Accepted
time: 2ms
memory: 6724kb

input:

100 300 30
82 18
88 8
36 33
31 62
41 5
82 3
2 51
94 74
34 36
53 11
21 74
80 39
82 32
97 36
75 45
38 10
43 1
99 16
94 97
8 49
12 6
9 77
55 30
51 40
71 33
22 93
52 84
97 27
24 31
100 89
79 60
90 50
67 24
71 18
71 67
13 19
40 45
2 27
25 30
86 51
38 82
24 35
29 54
9 42
72 91
57 10
75 11
15 46
23 98
72 9...

output:

0
0
1
1
1
2
2
2
2
3
3
3
3
3
3
3
4
4
5
6
6
6
6
6
7
7
7
7
7
7

result:

ok 30 lines

Test #3:

score: 12
Accepted
time: 2ms
memory: 6660kb

input:

100 4000 30
10 37
33 68
31 45
1 32
51 12
79 50
28 60
84 24
88 85
5 4
54 24
84 10
57 80
46 22
45 3
51 70
88 14
38 4
20 18
31 88
48 53
60 78
23 100
60 67
47 92
12 68
22 100
65 22
88 28
86 66
31 29
63 32
87 10
59 14
55 71
50 35
80 67
37 76
32 68
36 6
59 79
20 83
4 75
75 11
93 53
70 63
38 76
75 100
53 9...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 30 lines

Test #4:

score: 12
Accepted
time: 0ms
memory: 6696kb

input:

100 299 30
80 99
19 21
96 80
25 31
35 21
45 26
70 77
24 30
80 98
1 6
66 70
85 92
77 84
86 87
22 26
81 80
76 99
14 10
71 75
29 20
97 93
58 49
42 59
80 83
61 62
65 70
26 11
82 85
32 46
89 85
44 59
71 70
20 31
62 60
77 87
81 94
88 78
99 77
35 52
90 83
76 89
17 23
2 14
54 62
26 23
90 85
27 61
86 79
44 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2

result:

ok 30 lines

Test #5:

score: 12
Accepted
time: 1ms
memory: 4516kb

input:

100 1224 30
20 15
43 67
40 37
44 41
64 54
69 62
83 90
94 90
35 46
62 47
53 65
21 59
12 28
73 74
65 48
47 16
59 30
22 34
60 40
56 54
53 29
36 10
33 25
12 33
20 44
13 30
51 55
15 34
59 27
30 42
34 14
42 26
15 37
84 89
55 41
18 45
44 29
31 17
10 25
58 19
13 28
31 14
2 7
46 55
38 33
29 49
100 99
26 54
5...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
2
3
4
5
5
5
5
5
5
5
5
5
5
5

result:

ok 30 lines

Test #6:

score: 12
Accepted
time: 1ms
memory: 6440kb

input:

100 320 30
3 4
54 51
40 38
36 38
22 23
52 51
82 85
56 60
70 74
89 88
77 75
57 62
95 94
62 56
28 26
45 46
8 12
19 18
77 80
95 92
55 53
41 44
79 80
80 83
30 34
65 63
46 49
87 88
19 21
46 48
9 12
67 65
61 63
68 66
74 71
57 58
31 29
41 39
19 17
90 88
61 65
12 14
48 43
7 10
52 58
10 9
60 65
67 70
7 11
75...

output:

0
1
2
3
4
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6

result:

ok 30 lines

Test #7:

score: 12
Accepted
time: 1ms
memory: 4496kb

input:

100 99 30
34 33
63 62
56 55
32 33
19 18
52 51
46 47
25 24
47 48
86 85
5 6
10 11
95 96
36 35
40 41
38 37
35 34
15 14
57 56
94 95
49 48
77 76
17 18
27 26
3 2
91 90
61 60
51 50
64 63
96 97
75 76
50 49
54 53
98 99
17 16
31 32
78 77
21 20
39 40
64 65
31 30
4 5
71 72
72 73
28 29
73 74
9 10
12 11
6 7
82 83...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

result:

ok 30 lines

Test #8:

score: 12
Accepted
time: 0ms
memory: 4456kb

input:

100 117 30
84 83
5 6
32 33
86 85
22 23
25 24
49 48
35 34
96 95
64 65
5 4
10 11
96 98
29 30
75 76
52 53
60 59
21 22
74 73
14 13
17 16
92 91
46 45
58 57
24 22
99 100
59 58
89 90
44 45
41 42
37 38
88 87
97 98
83 82
93 94
99 98
15 14
48 47
88 89
39 37
69 70
86 87
20 19
61 62
69 68
39 38
8 10
63 62
13 12...

output:

1
1
2
3
3
4
5
7
7
9
9
10
11
11
11
12
14
14
15
16
17
19
20
21
21
23
23
23
24
25

result:

ok 30 lines

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #9:

score: 0
Runtime Error

input:

100000 200000 30
65050 42131
67933 59857
39663 11823
7869 49877
7320 17118
19992 137
34144 72998
92093 94024
37468 2408
6545 95749
22893 34898
68252 65170
56599 71980
64517 25707
76452 82961
80713 63458
88550 42270
27382 71666
67790 70596
54223 80866
87247 82414
81458 90465
63263 88126
58114 7473
32...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #17:

score: 0
Runtime Error

input:

100000 200000 164
36182 13438
33869 82192
11340 90025
90981 21132
26395 63881
81566 99302
82105 47346
48532 41260
96423 51767
72741 14142
84801 24765
63748 16280
84541 18064
666 93607
86032 56008
78210 47709
91164 84768
32019 15397
98332 28388
90022 72299
28551 39055
96371 50829
46263 60518
53104 84...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%