Submission #956928

#	Time	Username	Problem	Language	Result	Execution time	Memory
956928		_callmelucian	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1038 ms	435004 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], iter[mn], n;

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

void process (int u) {
    int cnt = 0;
    for (int v : rev[u]) {
        if (best[v].size()) cnt++;
        iter[v] = 0;
    }
    while (cnt && best[u].size() < srt) {
        int ans = INT_MIN, save = 0;
        for (int v : rev[u]) {
            if (iter[v] == best[v].size()) continue;
            while (iter[v] < best[v].size() && check[best[v][iter[v]].second])
                iter[v]++;
            if (iter[v] == best[v].size()) {
                cnt--;
                continue;
            }
            int dist, node; tie(dist, node) = best[v][iter[v]];
            if (dist + 1 > ans) ans = dist + 1, save = v;
        }
        int dist, node; tie(dist, node) = best[save][iter[save]++];
        best[u].push_back(make_pair(dist + 1, node));
        check[node] = 1;
        if (iter[save] == best[save].size()) cnt--;
    }
    if (best[u].size() < srt)
        best[u].push_back(make_pair(0, u));

    for (pii it : best[u]) check[it.second] = 0;
}

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 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;
        }
    }

    // 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:56:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if (iter[v] == best[v].size()) continue;
      |                 ~~~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             while (iter[v] < best[v].size() && check[best[v][iter[v]].second])
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if (iter[v] == best[v].size()) {
      |                 ~~~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if (iter[save] == best[save].size()) cnt--;
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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