Submission #408205

#	Time	Username	Problem	Language	Result	Execution time	Memory
408205		Andyvanh1	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2099 ms	15292 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>


using namespace std;

#define vt vector
#define pb push_back

typedef long long ll;
typedef vt<int> vi;
typedef pair<int,int> pii;

int F;



vi adjlist[100005];
bool visited[100005];
stack<int> urev;
vi tpst;
int ans[100005];
bool big[100005];
bool cur[100005];
int sze[100005];
int val[100005];


void dfs(int node){
    visited[node] = true;
    for(auto& e: adjlist[node]){
        if(!visited[e])dfs(e);}
    urev.push(node);
}

void toposort(int n){
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            dfs(i);
        }
    }
}



struct qry{
    int node;
    int sz;
    vi arr;
    void init(int x, vi a){
        node = x;
        sz = a.size();
        for(int i = 0; i < sz; i++){
            arr.pb(a[i]);
        }
    }
};

void procbig(const qry& q,int index,int n){

    for(int i = 0; i < n; i++){
        cur[i] = true;
    }
    for(int i = 0; i < q.sz; i++){
        cur[q.arr[i]] = false;
    }
    for(int i = 0; i < n; i++){
        val[i] = 0;
    }
    for(int i = 0; i < n; i++){
        int x = tpst[i];
        if(!cur[x]&&val[x] == 0){
            continue;
        }
        for(auto& e: adjlist[x]){
            val[e] = max(val[e],val[x]+1);
        }
    }

        if(!cur[q.node]&&val[q.node]==0){

        ans[index] = -1;
        return;
    }
   ans[index] = val[q.node];


}


void solve(){
    int n, m, q;
    cin>>n>>m>>q;
    int k = (int)sqrt(q);
    for(int i = 0; i < m; i++){
        int u, v;
        cin>>u>>v;u--;v--;
        adjlist[u].pb(v);

    }
    toposort(n);

    while(!urev.empty()){
        tpst.push_back(urev.top());
        urev.pop();
    }
    vt<qry> queries(q);

    for(int i = 0; i < q; i++){
        int node;
        cin>>node;node--;
        int sz;
        cin>>sz;
        vi arr(sz);
        for(int j = 0; j < sz; j++){
            cin>>arr[j];
            arr[j]--;
        }
        queries[i].init(node,arr);

    }
    for(int i = 0; i < q; i++){
        if(1) {
            big[i] = true;
            procbig(queries[i], i, n);
        }
    }










for(int i = 0; i < q; i++){
    cout<<ans[i]<<'\n';
}

}

int main() {
    solve();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:100:9: warning: unused variable 'k' [-Wunused-variable]
  100 |     int k = (int)sqrt(q);
      |         ^

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86