Submission #656082

#	Time	Username	Problem	Language	Result	Execution time	Memory
656082		ParsaS	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1697 ms	433636 KiB

bitaro

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;

const int N = 1e5 + 5, MOD = 1e9 + 7, SQ = sqrt(N);
vector<int> adj[N], vec[N], Q[N];
int n, m, q, T[N], prv[N];
unordered_set<int> st[N];
int cur, dis[N], ans[N];
vector<pair<int, int> > V[N];

void _merge(int v, int u) {
    cur++;
    vector<pair<int, int> > tmp;

    int l = 0, r = 0;
    while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
        while (l < V[v].size() && prv[V[v][l].se] == cur)
            l++;
        while (r < V[u].size() && prv[V[u][r].se] == cur)
            r++;
        if (l == V[v].size() || r == V[u].size())
            break;
        pair<int, int> pl = V[v][l], pr = V[u][r];
        pr.fi++;
        if (pl >= pr) {
            tmp.pb(pl);
            prv[pl.se] = cur;
            l++;
        }
        else {
            tmp.pb(pr);
            prv[pr.se] = cur;
            r++;
        }
    }
    while (tmp.size() < SQ && l < V[v].size()) {
        while (l < V[v].size() && prv[V[v][l].se] == cur)
            l++;
        if (l == V[v].size())
            break;
        tmp.pb(V[v][l]);
        prv[V[v][l].se] = cur;
        l++;
    }
    while (tmp.size() < SQ && r < V[u].size()) {
        while (r < V[u].size() && prv[V[u][r].se] == cur) {
            r++;
        }
        if (r == V[u].size())
            break;

        tmp.pb(V[u][r]);
        tmp.back().fi++;
        prv[V[u][r].se] = cur;
        r++;
    }
    swap(V[v], tmp);
}
void brute_force(int r) {
    for (int j = 1; j <= r; j++)
        dis[j] = -1e9;
    dis[r] = 0;
    for (int i = r; i > 1; i--) {
        for (auto j : adj[i]) {
            dis[j] = max(dis[j], dis[i] + 1);
        }
    }
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int s, e; cin >> s >> e;
        adj[e].pb(s);
    }
    for (int i = 0; i < q; i++) {
        cin >> T[i];
        int y; cin >> y;
        for (int j = 0; j < y; j++) {
            int x; cin >> x;
            if (x <= T[i])
                st[i].insert(x);
        }
        Q[T[i]].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        V[i].pb(mp(0, i));
        for (auto u : adj[i]) {
            _merge(i, u);
        }
        bool ok = false;
        vector<pair<int, int> > tmp;
        for (auto j : Q[i]) {
            if (st[j].size() >= SQ) {
                if (!ok) {
                    brute_force(i);
                    for (int k = 1; k <= i; k++)
                        if (dis[k] >= 0)
                            tmp.pb(mp(dis[k], k));
                    sort(tmp.begin(), tmp.end(), greater<pair<int, int> >());
                    ok = true;
                }
                int inx = 0;
                while (inx < tmp.size() && st[j].find(tmp[inx].se) != st[j].end()) {
                    inx++;
                }
                ans[j] = (inx == tmp.size() ? -1 : tmp[inx].fi);
            }
            else {
                int inx = 0;
                while (inx < V[i].size() && st[j].find(V[i][inx].se) != st[j].end())
                    inx++;
                ans[j] = (inx == V[i].size() ? -1 : V[i][inx].fi);
            }
        }
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void _merge(int, int)':
bitaro.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
      |            ~~^~~~~~~~~~~~~
bitaro.cpp:22:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         while (l < V[v].size() && prv[V[v][l].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while (r < V[u].size() && prv[V[u][r].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (l == V[v].size() || r == V[u].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp:27:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (l == V[v].size() || r == V[u].size())
      |                                 ~~^~~~~~~~~~~~~~
bitaro.cpp:42:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     while (tmp.size() < SQ && l < V[v].size()) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while (l < V[v].size() && prv[V[v][l].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (l == V[v].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp:51:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (tmp.size() < SQ && r < V[u].size()) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while (r < V[u].size() && prv[V[u][r].se] == cur) {
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (r == V[u].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:110: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]
  110 |                 while (inx < tmp.size() && st[j].find(tmp[inx].se) != st[j].end()) {
      |                        ~~~~^~~~~~~~~~~~
bitaro.cpp:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 ans[j] = (inx == tmp.size() ? -1 : tmp[inx].fi);
      |                           ~~~~^~~~~~~~~~~~~
bitaro.cpp:117: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]
  117 |                 while (inx < V[i].size() && st[j].find(V[i][inx].se) != st[j].end())
      |                        ~~~~^~~~~~~~~~~~~
bitaro.cpp:119:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                 ans[j] = (inx == V[i].size() ? -1 : V[i][inx].fi);
      |                           ~~~~^~~~~~~~~~~~~~

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