QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #299434 | #121. Bitaro's Party | Xttttr | 0 | 1ms | 8060kb | C++14 | 2.2kb | 2024-01-06 20:59:09 | 2024-01-06 20:59:11 |
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s;
}
inline void write(int x){
if(x>9)write(x/10);
putchar(x%10+48);
}
const int N=100501,B=75;
int n,m,Q;
int cnt,ver[N<<1],nxt[N<<1],h[N],in[N],out[N];
inline void add_edge(int x,int y){cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;in[y]++;out[x]++;}
vector<pair<int,int> >f[N];
int tmp[N];
bool mark[N];
inline void topo(){
for(int x=1;x<=n;x++){
for(int i=1;i<=out[x];i++)tmp[i]=0;
for(int j=0;j<B;j++){
pair<int,int>maxn=make_pair(-1,-1);
for(int i=h[x],id=1;i;i=nxt[i],id++){
int y=ver[i];
while(tmp[id]!=(int)f[y].size()&&mark[f[y][tmp[id]].first])tmp[id]++;
if(tmp[id]!=(int)f[y].size()){
if(f[y][tmp[id]].second>maxn.second)maxn=f[y][tmp[id]];
}
}
if(~maxn.first)maxn.second++,f[x].push_back(maxn),mark[maxn.first]=1;
else {
f[x].push_back({x,0});
break;
}
}
for(auto i:f[x])mark[i.first]=0;
// for(auto i:f[x])cout<<i.first<<" "<<i.second<<" ";
// cout<<endl;
}
}
int st[N],dis[N];
bool b[N];
int main(){
n=read(),m=read(),Q=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add_edge(y,x);
}
topo();
while(Q--){
int s=read(),k=read(),ans=-1;
for(int i=1;i<=k;i++)st[i]=read(),b[st[i]]=1;
if(k<B){
for(auto i:f[s])if(!b[i.first]){
ans=i.second;
break;
}
}
else{
queue<int>q;
dis[s]=0;
for(int x=s;x;x--){
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
dis[y]=max(dis[y],dis[x]+1);
}
if(!b[x])ans=max(ans,dis[x]);
}
}
if(~ans)write(ans),putchar('\n');
else puts("-1");
for(int i=1;i<=k;i++)b[st[i]]=0;
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 1ms
memory: 5996kb
input:
1 0 1 1 0
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
1 0 1 1 1 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7572kb
input:
2 1 1 1 2 1 2 1 2
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7520kb
input:
2 1 1 1 2 1 1 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: -7
Wrong Answer
time: 0ms
memory: 8060kb
input:
1000 2000 1 66 427 211 505 213 674 56 131 180 883 127 167 228 262 42 50 386 688 346 943 170 396 127 150 169 192 253 706 96 497 141 277 317 711 792 802 244 469 24 702 135 252 31 764 52 95 701 900 473 832 510 691 14 474 158 488 422 491 228 897 318 622 195 548 479 626 525 728 53 109 133 854 392 416 34 ...
output:
20
result:
wrong answer 1st lines differ - expected: '12', found: '20'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%