Submission #656078

#	Time	Username	Problem	Language	Result	Execution time	Memory
656078		ParsaS	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1439 ms	451504 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 = 2e5 + 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) {
    /*set<pair<int, int> > S;
    unordered_set<int> s;
    cur++;
    for (auto [x, y] : V[v]) {
        s.insert(y);
        if (prv[y] < cur || dis[y] < x) {
            dis[y] = x;
            prv[y] = cur;
        }
    }
    for (auto [x, y] : V[u]) {
        s.insert(y);
        if (prv[y] < cur || dis[y] < x + 1) {
            dis[y] = x + 1;
            prv[y] = cur;
        }
    }
    V[v].clear();
    for (auto x : s) {
        S.insert(mp(-dis[x], x)); 
    }
    while (!S.empty() && V[v].size() < SQ) {
        V[v].pb(mp(-S.begin()->fi, S.begin()->se));
        S.erase(S.begin());
    }
    return;*/
    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);
        }
        /*cout << i << " : ";
        for (auto x : V[i])
            cout << x.fi << ' ' << x.se << endl;*/
        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);
            }
        }
        /*if (ok) {
            vector<pair<int, int> > tmp;
            brute_force(i);
            for (int j = 1; j <= i; j++) {
                tmp.pb(mp(dis[j], j));
            }
            sort(tmp.begin(), tmp.end(), greater<pair<int, int> >());
            for (auto j : Q[i]) {
                
            }
        }*/
    }
    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:48: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]
   48 |     while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
      |            ~~^~~~~~~~~~~~~
bitaro.cpp:48: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]
   48 |     while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:49: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]
   49 |         while (l < V[v].size() && prv[V[v][l].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:51: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]
   51 |         while (r < V[u].size() && prv[V[u][r].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:53: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]
   53 |         if (l == V[v].size() || r == V[u].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp:53: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]
   53 |         if (l == V[v].size() || r == V[u].size())
      |                                 ~~^~~~~~~~~~~~~~
bitaro.cpp:68: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]
   68 |     while (tmp.size() < SQ && l < V[v].size()) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:69: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]
   69 |         while (l < V[v].size() && prv[V[v][l].se] == cur)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:71: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]
   71 |         if (l == V[v].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp:77: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]
   77 |     while (tmp.size() < SQ && r < V[u].size()) {
      |                               ~~^~~~~~~~~~~~~
bitaro.cpp:78: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]
   78 |         while (r < V[u].size() && prv[V[u][r].se] == cur) {
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:81: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]
   81 |         if (r == V[u].size())
      |             ~~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:139: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]
  139 |                 while (inx < tmp.size() && st[j].find(tmp[inx].se) != st[j].end()) {
      |                        ~~~~^~~~~~~~~~~~
bitaro.cpp:142: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]
  142 |                 ans[j] = (inx == tmp.size() ? -1 : tmp[inx].fi);
      |                           ~~~~^~~~~~~~~~~~~
bitaro.cpp:146: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]
  146 |                 while (inx < V[i].size() && st[j].find(V[i][inx].se) != st[j].end())
      |                        ~~~~^~~~~~~~~~~~~
bitaro.cpp:148: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]
  148 |                 ans[j] = (inx == V[i].size() ? -1 : V[i][inx].fi);
      |                           ~~~~^~~~~~~~~~~~~~

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