QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799162 | #3148. Train Fare | modwwe | 12 | 2ms | 6724kb | C++23 | 2.8kb | 2024-12-04 23:56:59 | 2024-12-04 23:57:00 |
Judging History
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%