Submission #1103693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103693		ortsac	Political Development (BOI17_politicaldevelopment)	C++17	77 / 100	3079 ms	94660 KiB

politicaldevelopment

#pragma GCC optmize("O3")
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define fr first
#define se second

const int MAXN = 5e4 + 10;

deque<int> oldAdj[MAXN];
deque<int> adj[MAXN]; 

void merge(deque<int>& v1, deque<int>& v2, deque<int>& res) {
    int n = v1.size(), m = v2.size();
    int p1 = 0, p2 = 0;
    while ((p1 < n) && (p2 < m)) {
        if (v1[p1] == v2[p2]) {
            res.push_back(v1[p1]);
            p1++;
            p2++;
            continue;
        }
        if (v1[p1] < v2[p2]) p1++;
        else p2++;
    }
}

int best(deque<int> pos) {
    int mx = 0;
    while (!pos.empty()) {
        auto u = pos.front();
        pos.pop_front();
        deque<int> nxt;
        merge(pos, adj[u], nxt);
        mx = max(mx, 1 + best(nxt));
    }
    return mx;
}

int32_t main() {
    int n, k;
    cin >> n >> k;
    vector<pii> ord;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ord.push_back({x, i});
        while (x--) {
            int v;
            cin >> v;
            oldAdj[i].push_back(v);
        }
        //sort(adj[i].begin(), adj[i].end());
    }
    vector<int> nname(n);
    sort(ord.begin(), ord.end());
    for (int i = 0; i < n; i++) nname[ord[i].se] = i;
    for (int i = 0; i < n; i++) {
        adj[nname[i]] = oldAdj[i];
        for (auto& u : adj[nname[i]]) u = nname[u];
        sort(adj[nname[i]].begin(), adj[nname[i]].end()); 
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, best(adj[i]) + 1);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

politicaldevelopment.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    1 | #pragma GCC optmize("O3")
      |

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 0 / 23