QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799160 | #3148. Train Fare | modwwe | 0 | 2ms | 6732kb | C++23 | 2.8kb | 2024-12-04 23:46:21 | 2024-12-04 23:46:22 |
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,n+1};
for(int i=2; i<=n; i++)
dp[i].a=inf,dp[i].b=n+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,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]=n+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: 0
Wrong Answer
Test #1:
score: 12
Accepted
time: 1ms
memory: 6368kb
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: 0ms
memory: 4392kb
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: 6728kb
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: 0
Wrong Answer
time: 0ms
memory: 6732kb
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 1 1 1 1 1 1
result:
wrong answer 25th lines differ - expected: '2', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
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:
0%