QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299434#121. Bitaro's PartyXttttr0 1ms8060kbC++142.2kb2024-01-06 20:59:092024-01-06 20:59:11

Judging History

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

  • [2024-01-06 20:59:11]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:8060kb
  • [2024-01-06 20:59:09]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%