Submission #956919

#	Time	Username	Problem	Language	Result	Execution time	Memory
956919		_callmelucian	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2059 ms	363036 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int srt = 310;

struct query {
    int id;
    vector<int> block;

    query() : id(0) {}
    query (int x, vector<int> v) : id(x), block(v) {}
};

vector<int> adj[mn], rev[mn], line, lineRev;
bool vis[mn], check[mn];

void dfs (int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (int v : adj[u]) dfs(v);
    line.push_back(u);
}

void dfsRev (int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (int v : rev[u]) dfsRev(v);
    lineRev.push_back(u);
}

vector<query> qry[mn];
vector<pii> best[mn];
int dp[mn], ans[mn], n;

bool compare (pii a, pii b) { return a.first > b.first; }

void process (int u) {
    sort(all(best[u]), compare);
    vector<pii> vec;
    for (int i = 0; i < best[u].size() && vec.size() < srt; i++) {
        int dist, st; tie(dist, st) = best[u][i];
        if (check[st]) continue;
        vec.push_back(best[u][i]);
        check[st] = 1;
    }
    for (pii it : vec) check[it.second] = 0;
    best[u] = vec;
}

int dpCalc (int st, vector<int> &block) {
    for (int u : block) check[u] = 1;
    for (int i = 1; i <= n; i++) dp[i] = INT_MIN;
    dp[st] = 0; int ans = INT_MIN;
    for (int u : lineRev) {
        for (int v : adj[u])
            if (dp[v] != INT_MIN) dp[u] = max(dp[u], dp[v] + 1);
        if (!check[u]) ans = max(ans, dp[u]);
    }
    for (int u : block) check[u] = 0;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m, q; cin >> n >> m >> q;
    while (m--) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        rev[b].push_back(a);
    }

    // prepare topological sorting
    for (int i = 1; i <= n; i++) dfs(i);
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) dfsRev(i);
    reverse(all(line)); reverse(all(lineRev));

    // read queries and process big ones
    for (int i = 0; i < q; i++) {
        int v, k; cin >> v >> k;
        vector<int> vec(k);
        for (int j = 0; j < k; j++) cin >> vec[j];
        if (k < srt)
            qry[v].push_back(query(i, vec));
        else ans[i] = dpCalc(v, vec);
    }

    // process small queries
    for (int i = 1; i <= n; i++)
        best[i].push_back(make_pair(0, i));

    for (int u : line) {
        process(u);
        for (query &it : qry[u]) {
            for (int node : it.block) check[node] = 1;
            bool ready = 0;
            for (pii iter : best[u]) {
                if (check[iter.second]) continue;
                ans[it.id] = iter.first, ready = 1;
                break;
            }
            if (!ready) ans[it.id] = INT_MIN;
            for (int node : it.block) check[node] = 0;
        }

        for (int v : adj[u]) {
            for (pii it : best[u]) {
                int dist, node; tie(dist, node) = it;
                best[v].push_back(make_pair(dist + 1, node));
            }
        }
    }

    // print answers
    for (int i = 0; i < q; i++) cout << (ans[i] == INT_MIN ? -1 : ans[i]) << "\n";

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void process(int)':
bitaro.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < best[u].size() && vec.size() < srt; i++) {
      |                     ~~^~~~~~~~~~~~~~~~

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