Submission #718077

#	Time	Username	Problem	Language	Result	Execution time	Memory
718077		Johann	Political Development (BOI17_politicaldevelopment)	C++14	0 / 100	2 ms	452 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i,n) for (int i = 0; i < (n); ++i)

int MAXK = 10;

void dfs(vvi & adj, int v, int p, vi & honstack, vb & visited, vi & maxKpos, int & ansK) {
    cout << "dfs: " << v << "\n";
    visited[v] = true;
    honstack[v] = honstack[p] + 1;
    vi howMuch(MAXK, -1);
    for (int w : adj[v]) {
        if (honstack[w] != -1) {
            int dist = honstack[v] - honstack[w];
            if (dist < MAXK) howMuch[dist] = w;
        }
    }
    for (maxKpos[v] = MAXK; maxKpos[v] > 0; --maxKpos[v]) {
        bool possible = true;
        for (int i = 1; i < maxKpos[v]; ++i) {
            if (!howMuch[i]) { possible = false; break; }
            if (maxKpos[howMuch[i]] < maxKpos[v] - i) {
                possible = false; break;
            }
        }
        if (possible) break;
    }
    ansK = max(ansK, maxKpos[v]);
    for (int w : adj[v]) {
        if (!visited[w]) {
            dfs(adj, w, v, honstack, visited, maxKpos, ansK);
        }
    }
    honstack[v] = -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N,K;
    cin >> N >> K;
    MAXK = K;
    vvi adj(N);
    F0R(v,N) {
        int di;
        cin >> di;
        adj[v].resize(di);
        F0R(i,di) cin >> adj[v][i];
    }

    int ans = 1;
    vi honstack(N, -1);
    vi maxKpos(N, 1);
    vb visited(N, false);
    F0R(v,N) {
        if (!visited[v]) {
            dfs(adj, v, v, honstack, visited, maxKpos, ans);
        }
    }

    cout << ans << endl;
}

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