제출 #1286425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286425		samarthkulkarni	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2095 ms	21948 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize("fast-math")

#define ll long long
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};


void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int MAXN = 1e5+10;
vi adj[MAXN];
vi radj[MAXN];
bool vis[MAXN];
ll n;



vi ord;
void dfs(ll a) {
    vis[a] = true;
    for (auto b : adj[a]) {
        if (vis[b]) continue;
        dfs(b);
    }
    ord.push_back(a);
}


ll calculate(ll T, vi &temp) {

    vi dist(n+1);
    for (auto val : temp) dist[val] = -1;

    for (auto a : ord) {

        for (auto b : radj[a]) {
            if (dist[b] == -1) continue;

            dist[a] = max(dist[b]+1, dist[a]);
        }

    }

    return dist[T];
}

void solution() {
    ll m, q; cin >> n >> m >> q;
    while (m--) {
        ll a, b; cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }




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

    reverse(all(ord));

    while (q--) {
        ll t, y; cin >> t >> y;
        vi temp(y);
        for (ll &z : temp) cin >> z;
        cout << calculate(t, temp) << endl;
    }


}

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