oj.uz

Submission #718077

# Submission time Handle Problem Language Result Execution time Memory
718077 2023-04-03T09:44:06 Z Johann Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 2 ms 452 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -