제출 #830634

#제출 시각아이디문제언어결과실행 시간메모리
830634JohannPolitical Development (BOI17_politicaldevelopment)C++14
0 / 100
1 ms500 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...