QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788696#9810. Obliviate, Then Reincarnatelilab#WA 1ms5912kbC++203.1kb2024-11-27 17:56:322024-11-27 17:56:32

Judging History

This is the latest submission verdict.

  • [2024-11-27 17:56:32]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5912kb
  • [2024-11-27 17:56:32]
  • Submitted

answer

#include<bits/stdc++.h>
// using namespace std;
using ll=long long;
#define int ll

const ll N=5e5+100;

struct gra{
    struct data{ int to, next, w; };
    std::vector<int> head;
    std::vector<data> e;
    int tot;
    void ini( int n ){
        head.clear();e.clear();
        head.resize( n + 1 );e.resize( 1 );
        tot = 0;
    }
    void add_e( int x, int y, int w = 1 ){
        e.push_back({y, head[ x ], w });
        head[ x ] = ++tot;
    }
}g, g1;
int n, m, Q ;
int dfn[ N ], low[ N ], dfnnum;
std::vector<int> st;
int ins[ N ], scc[ N ], scccnt, size[ N ];
void tarjan( int x ){
    st.push_back( x );
    ins[ x ] = 1;
    dfn[ x ] = low[ x ] = ++dfnnum;
    for( int i = g.head[ x ] ; i ; i = g.e[ i ].next ){
        int y = g.e[ i ].to;
        if( !dfn[ y ] ){
            tarjan( y );
            low[ x ] = std::min( low[ x ], low[ y ] );
        }else{
            if( ins[ y ] ) low[ x ] = std::min( low[ x ], dfn[ y ] );
        }
    }

    if( dfn[ x ] == low[ x ] ){
        int y ; ++scccnt;
        do{
            y = st.back();ins[ y ] = 0;
            st.pop_back();
            scc[ y ] = scccnt;
            size[ scccnt ] ++;
        }while( x != y );
    }
}

std::vector<std::pair<int,int>> es;

void solve(){
    std::cin>>n>>m>>Q;
    g.ini( n );
    std::vector<int> selfloop( n + 1 );
    for( int i = 1 ; i <= m ; i ++ ){
        int x, y;std::cin>>x>>y;
        if( y == 0 ) continue;
        y += x;
        x = (x % n + n) % n;
        y = (y % n + n) % n;
        x ++;
        y ++;
        es.push_back( {x, y});
        g.add_e( x, y );  
        if( x == y ) selfloop[ x ] = 1;
    }

    for( int i = 1 ; i <= n ; i ++ ){
        if( !dfn[ i ] ) tarjan( i );
    }

    g1.ini( scccnt );

    std::vector<int> bj( scccnt + 1 ), in( scccnt + 1 );

    for( int i = 1 ; i <= n ; i ++ ){
        if( size[ scc[ i ] ] != 1 || selfloop[ i ] ) bj[ scc[ i ] ] = 1;
    }

    for( auto t : es ){
        if( scc[ t.first ] == scc[ t.second ] ) continue;
        g1.add_e( scc[ t.second ], scc[ t.first ] );
        in[ scc[ t.first ] ] ++;
    }

    std::queue<int> q;
    for( int i = 1 ; i <= scccnt ; i ++ ){
        if( in[ i ] == 0 ){
            q.push( i );
        }
    }

    while( q.size() ){
        int x = q.front();
        q.pop();
        for( int i = g1.head[ x ]; i; i = g1.e[ i ].next ){
            int y = g1.e[ i ].to;
            bj[ y ] |= bj[ x ];
        }
    }

    std::vector<int> ans( n + 1 );

    for( int i = 1 ; i <= n ; i ++ ){
        if( bj[ scc[ i ] ] ) ans[ i ] = 1;
    }

    while( Q-- ){
        int x;std::cin>>x;
        x = ( x % n + n ) % n;
        x ++;
        if( ans[ x ] ){
            std::cout<<"Yes\n";
        }else{
            std::cout<<"No\n";
        }
    }
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t_=1;
    // std::cin>>t_;
    while(t_--)solve();
}
/*
3 2 3
1 1
-1 3
1
2
3

3 2 3
1 1
-1 0
1
2
3

3 3 3
1 1
2 2
1 2
1 
2 
3

3 3 3
1 1
2 2
3 1
1 
2 
3
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5636kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

Yes
Yes
No

result:

ok 3 tokens

Test #2:

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5632kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'