QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299443#121. Bitaro's PartyXttttr0 4ms7984kbC++142.2kb2024-01-06 21:01:022024-01-06 21:01:02

Judging History

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

  • [2024-01-06 21:01:02]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:7984kb
  • [2024-01-06 21:01:02]
  • 提交

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;
            for(int i=s;i;i--)dis[i]=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: 0ms
memory: 7508kb

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7516kb

input:

1 0 1
1 1 1

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7604kb

input:

2 1 1
1 2
1 2 1 2

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 7608kb

input:

2 1 1
1 2
1 1 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: -7
Wrong Answer
time: 4ms
memory: 7984kb

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%