| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1234261 | hashdfdfh | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long lonng
const int MAX_N = 200005;
const int B = 150; // Threshold for small/large Y_j
vector<int> graph[MAX_N]; // Original graph (u -> v)
vector<int> reverseGraph[MAX_N]; // Reverse graph (v -> u)
vector<pair<int, int>> longestPaths[MAX_N]; // longestPaths[u]: top B paths (distance, node)
bool isForbidden[MAX_N]; // Marks forbidden nodes during queries
bool visited[MAX_N]; // Temporary marker for mergePaths
int inDegree[MAX_N]; // In-degree for topological sort
// Merges two path lists and keeps top B paths
vector<pair<int, int>> mergePaths(const vector<pair<int, int>>& pathsA,
const vector<pair<int, int>>& pathsB) {
vector<pair<int, int>> merged;
int i = 0, j = 0;
while ((i < pathsA.size() || j < pathsB.size()) && merged.size() < B) {
if (i == pathsA.size()) {
if (!visited[pathsB[j].second]) {
visited[pathsB[j].second] = true;
merged.push_back(pathsB[j]);
}
j++;
continue;
}
if (j == pathsB.size()) {
if (!visited[pathsA[i].second]) {
visited[pathsA[i].second] = true;
merged.push_back({pathsA[i].first + 1, pathsA[i].second});
}
i++;
continue;
}
if (pathsA[i].first + 1 > pathsB[j].first) {
if (!visited[pathsA[i].second]) {
visited[pathsA[i].second] = true;
merged.push_back({pathsA[i].first + 1, pathsA[i].second});
}
i++;
} else {
if (!visited[pathsB[j].second]) {
visited[pathsB[j].second] = true;
merged.push_back(pathsB[j]);
}
j++;
}
}
// Reset visited markers
for (const auto& p : merged) visited[p.second] = false;
return merged;
}
// Computes longest paths from all nodes to 'target' (skipping forbidden nodes)
int computeLongestPath(int target, const vector<int>& forbiddenNodes) {
vector<int> maxDistance(MAX_N, -1);
vector<int> tempInDegree(MAX_N, 0);
queue<int> q;
// Initialize in-degree and forbidden nodes
for (int u = 1; u < MAX_N; u++) {
tempInDegree[u] = inDegree[u];
if (isForbidden[u]) maxDistance[u] = -1;
}
// Initialize DP: target node has distance 0
maxDistance[target] = 0;
// Topological sort with reverse graph
for (int u = 1; u < MAX_N; u++) {
if (tempInDegree[u] == 0 && !isForbidden[u]) {
q.push(u);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : reverseGraph[u]) {
if (isForbidden[v]) continue;
if (maxDistance[u] >= 0) {
maxDistance[v] = max(maxDistance[v], maxDistance[u] + 1);
}
tempInDegree[v]--;
if (tempInDegree[v] == 0) {
q.push(v);
}
}
}
// Find maximum distance among allowed nodes
int result = -1;
for (int u = 1; u < MAX_N; u++) {
if (!isForbidden[u]) result = max(result, maxDistance[u]);
}
return result;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
// Build graph and reverse graph
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
reverseGraph[v].push_back(u);
inDegree[v]++;
}
// Preprocess top B longest paths for each node (topological order)
queue<int> topoQueue;
for (int u = 1; u <= n; u++) {
if (inDegree[u] == 0) topoQueue.push(u);
longestPaths[u].push_back({0, u});
}
while (!topoQueue.empty()) {
int u = topoQueue.front(); topoQueue.pop();
for (int v : graph[u]) {
longestPaths[v] = mergePaths(longestPaths[u], longestPaths[v]);
inDegree[v]--;
if (inDegree[v] == 0) topoQueue.push(v);
}
}
// Process queries
while (q--) {
int target, k;
cin >> target >> k;
vector<int> forbiddenNodes(k);
for (int i = 0; i < k; i++) {
cin >> forbiddenNodes[i];
isForbidden[forbiddenNodes[i]] = true;
}
if (k >= B) {
// Large Y_j: Compute longest path dynamically
cout << computeLongestPath(target, forbiddenNodes) << "\n";
} else {
// Small Y_j: Use preprocessed paths
int maxDist = -1;
for (const auto& p : longestPaths[target]) {
if (!isForbidden[p.second]) {
maxDist = p.first;
break;
}
}
cout << maxDist << "\n";
}
// Reset forbidden markers
for (int node : forbiddenNodes) isForbidden[node] = false;
}
return 0;
}