답안 #830619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830619	2023-08-19T08:37:11 Z	Johann	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	컴파일 오류	0 ms	0 KB

garden

#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:10:17: error: 'INT_MAX' was not declared in this scope
   10 | const int INF = INT_MAX - 2;
      |                 ^~~~~~~
garden.cpp:1:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
  +++ |+#include <climits>
    1 | #define pii pair<int,int>
garden.cpp:1:13: error: 'pair' does not name a type
    1 | #define pii pair<int,int>
      |             ^~~~
garden.cpp:12:1: note: in expansion of macro 'pii'
   12 | pii minHelp(pii caint) {
      | ^~~
garden.cpp:1:13: error: 'pair' does not name a type
    1 | #define pii pair<int,int>
      |             ^~~~
garden.cpp:15:1: note: in expansion of macro 'pii'
   15 | pii dfs(vvpii & adj, int v, int P, int c, vvpii & dp) {
      | ^~~
garden.cpp:1:13: error: 'pair' has not been declared
    1 | #define pii pair<int,int>
      |             ^~~~
garden.cpp:34:23: note: in expansion of macro 'pii'
   34 | bool isInCycle(int K, pii start, pii P0, pii P1) {
      |                       ^~~
garden.cpp:1:17: error: expected ',' or '...' before '<' token
    1 | #define pii pair<int,int>
      |                 ^
garden.cpp:34:23: note: in expansion of macro 'pii'
   34 | bool isInCycle(int K, pii start, pii P0, pii P1) {
      |                       ^~~
garden.cpp: In function 'bool isInCycle(int, int)':
garden.cpp:35:10: error: 'start' was not declared in this scope
   35 |     K -= start.first;
      |          ^~~~~
garden.cpp:38:13: error: 'P0' was not declared in this scope
   38 |         if (P0.second == 0) return (K % P0.first) == 0;
      |             ^~
garden.cpp:39:14: error: 'P0' was not declared in this scope
   39 |         K -= P0.first;
      |              ^~
garden.cpp:43:13: error: 'P1' was not declared in this scope
   43 |         if (P1.second == 1) return (K % P1.first) == 0;
      |             ^~
garden.cpp:44:14: error: 'P1' was not declared in this scope
   44 |         K -= P1.first;
      |              ^~
garden.cpp:47:13: error: 'P0' was not declared in this scope
   47 |         if (P0.second == 0) {
      |             ^~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:4:15: error: 'vector' was not declared in this scope
    4 | #define vvpii vector<vpii>
      |               ^~~~~~
garden.cpp:58:5: note: in expansion of macro 'vvpii'
   58 |     vvpii adj(N);
      |     ^~~~~
garden.cpp:1:13: error: 'pair' was not declared in this scope
    1 | #define pii pair<int,int>
      |             ^~~~
garden.cpp:2:21: note: in expansion of macro 'pii'
    2 | #define vpii vector<pii>
      |                     ^~~
garden.cpp:4:22: note: in expansion of macro 'vpii'
    4 | #define vvpii vector<vpii>
      |                      ^~~~
garden.cpp:58:5: note: in expansion of macro 'vvpii'
   58 |     vvpii adj(N);
      |     ^~~~~
garden.cpp:1:18: error: expected primary-expression before 'int'
    1 | #define pii pair<int,int>
      |                  ^~~
garden.cpp:2:21: note: in expansion of macro 'pii'
    2 | #define vpii vector<pii>
      |                     ^~~
garden.cpp:4:22: note: in expansion of macro 'vpii'
    4 | #define vvpii vector<vpii>
      |                      ^~~~
garden.cpp:58:5: note: in expansion of macro 'vvpii'
   58 |     vvpii adj(N);
      |     ^~~~~
garden.cpp:61:16: error: 'adj' was not declared in this scope
   61 |         if (sz(adj[a]) < 2) adj[a].push_back({b, i});
      |                ^~~
garden.cpp:8:22: note: in definition of macro 'sz'
    8 | #define sz(x) ((int)(x).size())
      |                      ^
garden.cpp:62:16: error: 'adj' was not declared in this scope
   62 |         if (sz(adj[b]) < 2) adj[b].push_back({a, i});
      |                ^~~
garden.cpp:8:22: note: in definition of macro 'sz'
    8 | #define sz(x) ((int)(x).size())
      |                      ^
garden.cpp:65:16: error: 'adj' was not declared in this scope
   65 |         if (sz(adj[i]) != 2) adj[i].push_back(adj[i][0]);
      |                ^~~
garden.cpp:8:22: note: in definition of macro 'sz'
    8 | #define sz(x) ((int)(x).size())
      |                      ^
garden.cpp:1:18: error: expected primary-expression before 'int'
    1 | #define pii pair<int,int>
      |                  ^~~
garden.cpp:2:21: note: in expansion of macro 'pii'
    2 | #define vpii vector<pii>
      |                     ^~~
garden.cpp:4:22: note: in expansion of macro 'vpii'
    4 | #define vvpii vector<vpii>
      |                      ^~~~
garden.cpp:67:5: note: in expansion of macro 'vvpii'
   67 |     vvpii dp(N, vpii(2, { -1, -1 }));
      |     ^~~~~
garden.cpp:67:35: error: expected primary-expression before ')' token
   67 |     vvpii dp(N, vpii(2, { -1, -1 }));
      |                                   ^
garden.cpp:69:13: error: 'adj' was not declared in this scope
   69 |         dfs(adj, v, P, -1, dp);
      |             ^~~
garden.cpp:69:28: error: 'dp' was not declared in this scope
   69 |         dfs(adj, v, P, -1, dp);
      |                            ^~
garden.cpp:69:9: error: 'dfs' was not declared in this scope
   69 |         dfs(adj, v, P, -1, dp);
      |         ^~~
garden.cpp:6:13: error: 'map' was not declared in this scope
    6 | #define mii map<int,int>
      |             ^~~
garden.cpp:72:5: note: in expansion of macro 'mii'
   72 |     mii cnts0, cnts1; // 1 für, ja er kommt vom höchstbewerteten zu P
      |     ^~~
garden.cpp:6:17: error: expected primary-expression before 'int'
    6 | #define mii map<int,int>
      |                 ^~~
garden.cpp:72:5: note: in expansion of macro 'mii'
   72 |     mii cnts0, cnts1; // 1 für, ja er kommt vom höchstbewerteten zu P
      |     ^~~
garden.cpp:76:9: error: 'tie' was not declared in this scope
   76 |         tie(steps, last) = dp[v][0];
      |         ^~~
garden.cpp:76:28: error: 'dp' was not declared in this scope
   76 |         tie(steps, last) = dp[v][0];
      |                            ^~
garden.cpp:78:20: error: 'max' was not declared in this scope
   78 |         maxSteps = max(maxSteps, steps);
      |                    ^~~
garden.cpp:79:26: error: 'cnts1' was not declared in this scope
   79 |         if (last == 1) ++cnts1[steps];
      |                          ^~~~~
garden.cpp:80:16: error: 'cnts0' was not declared in this scope
   80 |         else ++cnts0[steps];
      |                ^~~~~
garden.cpp:83:5: error: 'dp' was not declared in this scope
   83 |     dp[P][0] = minHelp(dfs(adj, adj[P][0].first, P, adj[P][0].second, dp));
      |     ^~
garden.cpp:83:28: error: 'adj' was not declared in this scope
   83 |     dp[P][0] = minHelp(dfs(adj, adj[P][0].first, P, adj[P][0].second, dp));
      |                            ^~~
garden.cpp:83:24: error: 'dfs' was not declared in this scope
   83 |     dp[P][0] = minHelp(dfs(adj, adj[P][0].first, P, adj[P][0].second, dp));
      |                        ^~~
garden.cpp:83:16: error: 'minHelp' was not declared in this scope
   83 |     dp[P][0] = minHelp(dfs(adj, adj[P][0].first, P, adj[P][0].second, dp));
      |                ^~~~~~~
garden.cpp:1:18: error: expected primary-expression before 'int'
    1 | #define pii pair<int,int>
      |                  ^~~
garden.cpp:90:14: note: in expansion of macro 'pii'
   90 |         for (pii ele : cnts1) {
      |              ^~~
garden.cpp:93:9: error: expected primary-expression before 'for'
   93 |         for (pii ele : cnts0) {
      |         ^~~
garden.cpp:92:10: error: expected ';' before 'for'
   92 |         }
      |          ^
      |          ;
   93 |         for (pii ele : cnts0) {
      |         ~~~
garden.cpp:93:9: error: expected primary-expression before 'for'
   93 |         for (pii ele : cnts0) {
      |         ^~~
garden.cpp:92:10: error: expected ')' before 'for'
   92 |         }
      |          ^
      |          )
   93 |         for (pii ele : cnts0) {
      |         ~~~
garden.cpp:90:13: note: to match this '('
   90 |         for (pii ele : cnts1) {
      |             ^
garden.cpp:1:18: error: expected primary-expression before 'int'
    1 | #define pii pair<int,int>
      |                  ^~~
garden.cpp:93:14: note: in expansion of macro 'pii'
   93 |         for (pii ele : cnts0) {
      |              ^~~
garden.cpp:96:9: error: 'answer' was not declared in this scope
   96 |         answer(ans);
      |         ^~~~~~
garden.cpp:97:5: error: expected primary-expression before '}' token
   97 |     }
      |     ^
garden.cpp:96:21: error: expected ')' before '}' token
   96 |         answer(ans);
      |                     ^
      |                     )
   97 |     }
      |     ~                
garden.cpp:93:13: note: to match this '('
   93 |         for (pii ele : cnts0) {
      |             ^
garden.cpp:97:5: error: expected primary-expression before '}' token
   97 |     }
      |     ^