#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
// AB HIER
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define mii map<int,int>
#define sz(x) ((int)(x).size())
const int INF = INT_MAX - 2;
pii minHelp(pii caint) {
return { min(INF, caint.first + 1), caint.second };
}
pii dfs(vvpii & adj, int v, int P, int c, vvpii & dp) {
int w0, c0;
tie(w0, c0) = adj[v][0];
int cameFromHighest = (c == c0);
if (dp[v][cameFromHighest].first == -2) return dp[v][cameFromHighest] = { INF, INF };
if (dp[v][cameFromHighest].first != -1) return dp[v][cameFromHighest];
dp[v][cameFromHighest].first = -2;
if (v == P) return dp[v][cameFromHighest] = { 0, cameFromHighest };
if (!cameFromHighest) { // ich kann den höchsten Pfad nehmen!
pii caint = dfs(adj, w0, P, c0, dp);
return dp[v][cameFromHighest] = minHelp(caint);
} else {
int w1, c1;
tie(w1, c1) = adj[v][1];
pii caint = dfs(adj, w1, P, c1, dp);
return dp[v][cameFromHighest] = minHelp(caint);
}
}
bool isInCycle(int K, pii start, pii P0, pii P1) {
K -= start.first;
if (K == 0) return true;
if (K >= 0 && start.second == 0) {
if (P0.second == 0) return (K % P0.first) == 0;
K -= P0.first;
start.second = 1;
}
if (K >= 0 && start.second == 1) {
if (P1.second == 1) return (K % P1.first) == 0;
K -= P1.first;
start.second = 0;
if (K < 0) return false;
if (P0.second == 0) {
return (K % P0.first) == 0;
} else {
int clen = P0.first + P1.first;
return (K % clen == 0 || (K-P0.first) % clen == 0);
}
}
return false;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
vvpii adj(N);
for (int i = 0; i < M; ++i) {
int a = R[i][0], b = R[i][1];
if (sz(adj[a]) < 2) adj[a].push_back({b, i});
if (sz(adj[b]) < 2) adj[b].push_back({a, i});
}
for (int i = 0; i < N; ++i) {
if (sz(adj[i]) != 2) adj[i].push_back(adj[i][0]);
}
vvpii dp(N, vpii(2, { -1, -1 }));
for (int v = 0; v < N; ++v) {
dfs(adj, v, P, -1, dp);
}
mii cnts0, cnts1; // 1 für, ja er kommt vom höchstbewerteten zu P
int maxSteps = 0;
for (int v = 0; v < N; ++v) {
int steps, last;
tie(steps, last) = dp[v][0];
if (steps == INF) continue;
maxSteps = max(maxSteps, steps);
if (last == 1) ++cnts1[steps];
else ++cnts0[steps];
}
dp[P][0] = minHelp(dfs(adj, adj[P][0].first, P, adj[P][0].second, dp));
dp[P][1] = minHelp(dfs(adj, adj[P][1].first, P, adj[P][1].second, dp));
int i;
int ans;
for (i = 0; i < Q; i++) {
ans = 0;
for (pii ele : cnts1) {
if (isInCycle(G[i], { ele.first, 1 }, dp[P][0], dp[P][1])) ans += ele.second;
}
for (pii ele : cnts0) {
if (isInCycle(G[i], { ele.first, 0 }, dp[P][0], dp[P][1])) ans += ele.second;
}
answer(ans);
}
}
Compilation message
garden.cpp:1:10: fatal error: grader.h: No such file or directory
1 | #include "grader.h"
| ^~~~~~~~~~
compilation terminated.
