oj.uz

Submission #956919

# Submission time Handle Problem Language Result Execution time Memory
956919 2024-04-02T16:42:47 Z _callmelucian Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 363036 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10656 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 7 ms 11388 KB Output is correct
6 Correct 6 ms 11356 KB Output is correct
7 Correct 6 ms 11132 KB Output is correct
8 Correct 30 ms 15996 KB Output is correct
9 Correct 29 ms 15992 KB Output is correct
10 Correct 29 ms 16196 KB Output is correct
11 Correct 22 ms 15192 KB Output is correct
12 Correct 10 ms 12632 KB Output is correct
13 Correct 21 ms 15196 KB Output is correct
14 Correct 20 ms 14504 KB Output is correct
15 Correct 10 ms 12376 KB Output is correct
16 Correct 19 ms 14172 KB Output is correct
17 Correct 18 ms 14256 KB Output is correct
18 Correct 11 ms 12456 KB Output is correct
19 Correct 19 ms 14172 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10656 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 7 ms 11388 KB Output is correct
6 Correct 6 ms 11356 KB Output is correct
7 Correct 6 ms 11132 KB Output is correct
8 Correct 30 ms 15996 KB Output is correct
9 Correct 29 ms 15992 KB Output is correct
10 Correct 29 ms 16196 KB Output is correct
11 Correct 22 ms 15192 KB Output is correct
12 Correct 10 ms 12632 KB Output is correct
13 Correct 21 ms 15196 KB Output is correct
14 Correct 20 ms 14504 KB Output is correct
15 Correct 10 ms 12376 KB Output is correct
16 Correct 19 ms 14172 KB Output is correct
17 Correct 18 ms 14256 KB Output is correct
18 Correct 11 ms 12456 KB Output is correct
19 Correct 19 ms 14172 KB Output is correct
20 Execution timed out 2059 ms 363036 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10656 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 7 ms 11388 KB Output is correct
6 Correct 6 ms 11356 KB Output is correct
7 Correct 6 ms 11132 KB Output is correct
8 Correct 30 ms 15996 KB Output is correct
9 Correct 29 ms 15992 KB Output is correct
10 Correct 29 ms 16196 KB Output is correct
11 Correct 22 ms 15192 KB Output is correct
12 Correct 10 ms 12632 KB Output is correct
13 Correct 21 ms 15196 KB Output is correct
14 Correct 20 ms 14504 KB Output is correct
15 Correct 10 ms 12376 KB Output is correct
16 Correct 19 ms 14172 KB Output is correct
17 Correct 18 ms 14256 KB Output is correct
18 Correct 11 ms 12456 KB Output is correct
19 Correct 19 ms 14172 KB Output is correct
20 Execution timed out 2059 ms 363036 KB Time limit exceeded
21 Halted 0 ms 0 KB -