QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #858502 | #9677. 基础博弈练习题 | Hanghang# | 20 | 91ms | 10172kb | C++20 | 866b | 2025-01-16 17:55:21 | 2025-01-16 17:55:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3003;
int n,m,k,rt,a[N],b[N];
vector<int>ve[N],G[N];
bool vis[N],f[N][N],ok[N][N];
void Dfs(int x)
{
G[rt].push_back(x);vis[x]=1;
for(int y:ve[x])if(!vis[y])Dfs(y);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=k;i++)cin>>b[i];
for(int i=1,x,y;i<=m;i++)cin>>x>>y,ve[x].push_back(y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)vis[j]=0;
rt=i;
for(int j:ve[i])if(!vis[j])Dfs(j);
}
for(int i=1;i<=n;i++)for(int j:G[i])if(a[j]==b[k])f[i][k]=1;
for(int t=k-1;t>=1;t--)
{
for(int i=1;i<=n;i++)for(int j:G[i])if(!f[j][t+1]&&a[j]==b[t])f[i][t]=1;
}
for(int i=1;i<=n;i++)
{
int s=0;
for(int j=1;j<=k;j++)if(f[i][j]){s=j;break;}
cout<<s-1<<" ";
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 5892kb
input:
83 93 13 8 9 10 7 7 7 6 3 1 10 6 2 5 7 1 3 4 2 1 10 7 4 8 9 2 2 1 9 2 5 1 7 8 6 1 9 9 10 4 1 2 9 2 3 4 2 9 10 8 1 4 1 8 4 1 4 4 7 4 8 2 9 2 5 2 2 3 3 8 5 2 9 3 10 8 8 1 6 6 1 6 7 10 7 5 10 3 2 2 7 4 8 7 6 6 5 56 36 33 41 32 62 37 7 6 53 41 13 9 36 44 77 38 62 76 16 72 5 40 13 55 60 5 78 72 45 13 44 ...
output:
0 -1 -1 -1 2 0 -1 7 0 -1 3 -1 0 0 1 -1 0 -1 0 0 -1 0 -1 2 -1 -1 -1 -1 -1 -1 0 0 0 -1 0 -1 3 0 0 0 0 0 -1 -1 -1 -1 0 0 0 -1 0 0 3 0 0 0 -1 -1 3 -1 0 0 0 0 0 8 -1 -1 1 -1 -1 0 3 4 -1 3 -1 3 -1 0 0 0 -1
result:
ok 83 numbers
Test #2:
score: 10
Accepted
time: 0ms
memory: 7936kb
input:
95 33 40 1 1 1 1 3 3 1 1 2 1 1 2 3 3 2 2 2 1 2 3 1 2 1 2 2 1 2 2 3 3 1 1 2 3 1 2 1 3 2 1 1 1 3 2 1 1 1 2 3 2 3 1 1 3 2 3 1 2 1 3 1 2 1 1 1 1 2 1 2 3 1 1 3 3 2 1 3 3 3 1 2 3 1 2 2 1 3 2 1 1 1 2 2 3 1 2 2 3 1 3 3 2 3 3 2 2 2 2 1 1 1 1 2 1 1 1 1 1 2 3 1 3 2 2 3 1 3 3 1 2 2 3 2 1 3 11 95 57 80 22 89 56 ...
output:
2 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 3 -1 -1 -1 -1 -1 -1 -1 3 -1 3 -1 -1 0 -1 3 3 -1 0 0 -1 2 -1 -1 0 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 0 -1 -1 2 -1 -1 -1 3 3 -1 -1 -1 0 -1 -1 -1 -1 3 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 3 0 -1 -1 -1 -1 2 -1 0 0
result:
ok 95 numbers
Test #3:
score: 10
Accepted
time: 0ms
memory: 5684kb
input:
94 34 89 20 7 5 8 18 12 5 15 19 1 15 7 5 6 14 19 9 19 11 11 16 20 17 5 12 8 14 2 10 19 10 1 1 6 19 18 9 14 19 16 1 6 8 10 18 8 1 17 3 9 17 9 1 16 9 15 1 15 20 10 6 14 11 9 5 18 14 20 13 18 13 18 8 1 1 8 10 5 14 5 8 16 1 14 9 7 3 20 9 20 18 17 11 18 14 2 20 16 9 12 9 4 15 4 9 20 16 18 20 7 18 19 15 5...
output:
-1 19 -1 -1 -1 -1 -1 13 -1 -1 17 -1 -1 -1 26 -1 -1 2 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 33 2 -1 33 -1 -1 42 -1 -1 -1 -1 2 -1 -1 39 -1 -1 33 8 -1 -1 -1 -1 -1 -1 19 -1 -1 -1 4 15 1 -1 26 61 4 -1 -1 2 -1 -1 3 13 -1 13 -1 -1 -1 -1 -1 0 -1 -1 -1 8 -1 -1 61 -1 -1 2 -1 -1
result:
ok 94 numbers
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 10
Accepted
time: 91ms
memory: 6912kb
input:
2498 1795 2498 63 29 161 58 131 5 165 91 155 175 6 60 113 130 5 114 127 138 143 161 1 53 6 168 21 7 120 88 141 2 126 117 128 156 140 3 138 66 102 77 23 58 1 53 167 64 84 9 65 4 39 162 155 140 137 139 159 140 150 149 69 85 22 102 2 35 87 89 171 162 18 93 151 22 96 98 98 101 51 108 10 98 59 87 65 94 7...
output:
-1 -1 1599 -1 -1 0 1599 -1 -1 -1 0 -1 -1 -1 0 -1 1200 -1 -1 -1 0 -1 -1 1599 -1 0 -1 -1 -1 -1 1199 -1 -1 -1 1299 0 1299 -1 -1 -1 200 499 0 499 -1 -1 -1 -1 -1 -1 -1 -1 -1 1299 1299 -1 -1 -1 -1 1400 599 -1 -1 -1 -1 300 -1 -1 -1 -1 -1 900 -1 -1 900 -1 899 -1 -1 999 0 -1 -1 -1 -1 -1 -1 899 -1 -1 -1 1699 ...
result:
ok 2498 numbers
Test #5:
score: 10
Accepted
time: 20ms
memory: 10172kb
input:
1961 1528 1335 104 130 189 185 82 97 103 4 48 66 45 152 92 199 141 190 62 54 54 19 160 131 14 133 76 70 104 140 53 98 127 20 36 144 130 110 14 177 69 49 162 139 99 91 163 2 178 79 38 55 157 196 162 81 97 134 124 154 132 86 176 92 129 168 34 73 140 74 108 160 98 184 11 176 48 185 106 195 78 87 172 16...
output:
13 -1 8 -1 71 5 -1 43 -1 31 -1 29 -1 532 27 47 42 -1 -1 -1 4 623 15 -1 -1 -1 71 463 -1 7 2 -1 7 83 -1 532 -1 -1 16 -1 143 107 -1 47 -1 -1 -1 6 16 -1 -1 67 1 -1 315 255 -1 -1 38 -1 67 -1 -1 58 -1 304 -1 -1 3 -1 58 152 -1 96 -1 -1 48 1 -1 351 -1 -1 7 -1 -1 -1 46 -1 49 31 -1 -1 -1 -1 -1 -1 -1 15 42 140...
result:
ok 1961 numbers
Subtask #3:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
input:
100000 355071 10000 5 7 4 7 4 1 10 5 9 4 9 4 3 10 5 4 9 1 7 10 1 6 10 3 10 9 8 4 6 3 10 8 6 8 3 5 10 9 7 7 1 3 8 8 6 2 8 4 2 9 1 10 3 6 3 8 9 10 5 7 3 2 1 5 7 4 3 4 6 4 2 7 2 5 5 6 4 6 7 4 4 6 4 2 3 9 9 9 10 8 1 6 7 2 9 8 2 3 1 6 9 4 10 3 10 1 2 3 3 4 1 1 1 5 8 6 8 3 1 6 2 9 5 9 4 7 2 10 7 5 2 2 7 4...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st numbers differ - expected: '0', found: '-1'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%