oj.uz

Submission #656102

# Submission time Handle Problem Language Result Execution time Memory
656102 2022-11-06T09:49:25 Z mhn2 Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 32 ms 14064 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const int N = 1e5+5, SQ = 320, INF = 1e9;
int n, m, q;
int qt[N], mxy[N], dt[N], sn[N];
vector<int> g1[N], g2[N], qc[N];
vector<pii> mx[N];
list<pii> ls;
list<pii>::iterator ps[N];

void dist(int r) {
    for (int i = 1; i <= n; i++)
        dt[i] = -INF;
    dt[r] = 0;

    for (int i = r-1; i > 0; i--) {
        for (int u : g1[i])
            dt[i] = max(dt[i], dt[u]);
        dt[i]++;
    }
}

vector<pii> merge(vector<vector<pii>> a, int tm) {
    vector<pii> o, b, c;
    ls.clear();
    int r = INF;

    for (int i = 0; i < a.size(); i++)
        b.push_back({a[i].back().F, i});
    sort(b.begin(), b.end());

    for (int sib = b.size()-1; sib > -1; sib--) {
        int i = b[sib].S;

        if (b[sib].F < r) {
            for (int j = a[i].size()-1; j > -1; j--) {
                ls.push_front(a[i][j]);
                ps[a[i][j].F] = ls.begin();
                r = a[i][j].F;
            }
            continue;
        }
        
        for (int j = a[i].size()-1; j > -1; j--) {
            int x = a[i][j].F;
            ps[x] = ls.insert(ps[x], a[i][j]);
            r = min(r, x);
            if (x > 0 && x == r)
                ps[x-1] = ps[x];
        }
    }

    for (auto it = ls.begin(); it != ls.end(); it++)
        c.push_back(*it);

    for (int i = c.size()-1; i > -1; i--) {
        if (o.size() > SQ+3)
            break;
        if (sn[c[i].S] < tm) {
            o.push_back({c[i].F+1, c[i].S});
            sn[c[i].S] = tm;
        }
    }

    reverse(o.begin(), o.end());
    return o;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        g1[u].push_back(v);
        g2[v].push_back(u);
    }

    for (int i = 0; i < q; i++) {
        int y, z;
        cin >> qt[i] >> y;
        while (y--) {
            cin >> z;
            qc[i].push_back(z);
        }
        mxy[qt[i]] = max(mxy[qt[i]], y);
    }
    
    mx[1].push_back({1, 1});
    for (int i = 2; i <= n; i++)
        mx[i].push_back({0, i});
    for (int i = 2; i <= n; i++) {
        if (g2[i].size() == 0)
            continue;
        vector<vector<pii>> a;
        a.push_back(mx[i]);
        for (int v : g2[i])
            a.push_back(mx[v]);
        mx[i] = merge(a, i);
    }

    for (int i = 0; i < q; i++) {
        if (mxy[qt[i]] > SQ) {
            dist(qt[i]);
            int ans = -1, k = 0;
            for (int j = 1; j <= qt[i]; j++) {
                if (k < qc[i].size() && j == qc[i][k]) {
                    k++;
                    continue;
                }
                ans = max(dt[j], ans);
            }
            cout << ans << endl;
        }
        
        set<int> s;
        for (int x : qc[i])
            s.insert(x);

        int ans = -1, k = qc[i].size()-1;
        for (int j = mx[qt[i]].size()-1; j > -1; j--) {
            if (s.find(mx[qt[i]][j].S) == s.end()) {
                ans = mx[qt[i]][j].F - 1;
                break;
            }
            k--;
        }
        cout << ans << endl;
    }
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::vector<std::pair<int, int> > >, int)':
bitaro.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 if (k < qc[i].size() && j == qc[i][k]) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10456 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 12 ms 11092 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 9 ms 10964 KB Output is correct
8 Correct 31 ms 13964 KB Output is correct
9 Correct 32 ms 14064 KB Output is correct
10 Incorrect 31 ms 14036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10456 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 12 ms 11092 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 9 ms 10964 KB Output is correct
8 Correct 31 ms 13964 KB Output is correct
9 Correct 32 ms 14064 KB Output is correct
10 Incorrect 31 ms 14036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10456 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 12 ms 11092 KB Output is correct
6 Correct 9 ms 11092 KB Output is correct
7 Correct 9 ms 10964 KB Output is correct
8 Correct 31 ms 13964 KB Output is correct
9 Correct 32 ms 14064 KB Output is correct
10 Incorrect 31 ms 14036 KB Output isn't correct
11 Halted 0 ms 0 KB -