QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#827438#121. Bitaro's PartyRedDiamond#0 1ms3824kbC++113.0kb2024-12-22 23:05:202024-12-22 23:05:20

Judging History

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

  • [2024-12-22 23:05:20]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3824kb
  • [2024-12-22 23:05:20]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const int K = 320;


int n, m, q;
vector<vector<int>> g, gg;
vector<vector<pair<int, int>>> closest;
vector<int> vis, ord, dp;


void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    ord.push_back(u);
}


vector<bool> in;


void merge(vector<pair<int, int>> &a, vector<pair<int, int>> b) {
    vector<pair<int, int>> c = a;
    for (auto i : b) {
        c.push_back({i.first + 1, i.second});
    }
    sort(rall(c));
    vector<pair<int, int>> f;
    for (int i = 0; i < c.size(); i += 1) {
        if (in[c[i].second] == 1) {
            continue;
        }
        f.push_back({c[i].first, c[i].second});
        in[c[i].second] = 1;
        if (f.size() > K) {
            break;
        }
    }
    for (auto [x, y] : f) {
        in[y] = 0;
    }
    a = f;
}


void dfs2(int u) {
    for (auto v : gg[u]) {
        if (dp[u] + 1 > dp[v]) {
            dp[v] = max(dp[v], dp[u] + 1);
            dfs2(v);
        }
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
	}
	cin >> n >> m >> q;
    g.resize(n + 1);
    gg.resize(n + 1);
    for (int i = 1; i <= m; i += 1) {
        int e, s;
        cin >> e >> s;
        g[e].push_back(s);
        gg[s].push_back(e);
    }
    vis.assign(n + 1, 0);
    for (int i = 1; i <= n; i += 1) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    in.resize(n + 1);
    reverse(all(ord));
    closest.resize(n + 1);
    for (auto i : ord) {
        closest[i].push_back({0, i});
        for (auto v : gg[i]) {
            merge(closest[i], closest[v]);
        }
    }
   
    dp.resize(n + 1);
    vector<int> blocked(n + 1, 0);
    for (int iq = 1; iq <= q; iq += 1) {
        int t, y;
        cin >> t >> y;
        vector<int> v;
        for (int j = 0; j < y; j += 1) {
            int x;
            cin >> x;
            v.push_back(x);
            blocked[x] = 1;
        }
        if (y > K) {
            for (int i = 1; i <= n; i += 1) {
                dp[i] = -1;
            }
            dp[t] = 0;
            dfs2(t);
            int ans = -1;
            for (int i = 1; i <= n; i += 1) {
                if (blocked[i] == 0 && i != t) {
                    ans = max(ans, dp[i]);
                }
            }
            cout << ans << "\n";
        } else {
            int ans = -1;
            for (auto i : closest[t]) {
                if (!blocked[i.second] && i.second != t) {
                    ans = i.first;
                    break;
                }
            }
            cout << ans << "\n";
        }
        for (auto i : v) {
            blocked[i] = 0;
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3824kb

input:

1 0 1
1 0

output:

-1

result:

wrong answer 1st lines differ - expected: '0', found: '-1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%