Submission #1190636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190636		mehmetkagan	Tropical Garden (IOI11_garden)	C++20	Compilation error	0 ms	0 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int LOG = 30; // since 2^30 > 1e9
const int MAXN = 150005;

int N, M, P;
vector<int> adj[MAXN];
map<pair<int, int>, int> beauty; // ((u,v) -> beauty index)
int best[MAXN][2]; // best[u][0] = best neighbor, best[u][1] = 2nd best

int nxt[MAXN][MAXN]; // nxt[cur][prev] = deterministic next
int dp[LOG][MAXN][MAXN]; // dp[i][cur][prev] = number of ways to reach P in 2^i steps

void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
    N = n; M = m; P = p;

    // Build graph
    for (int i = 0; i < M; ++i) {
        int u = R[i][0], v = R[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
        beauty[{u, v}] = i;
        beauty[{v, u}] = i;
    }

    // Compute best and second-best neighbors
    for (int u = 0; u < N; ++u) {
        sort(adj[u].begin(), adj[u].end(), [&](int a, int b) {
            return beauty[{u, a}] < beauty[{u, b}];
        });
        best[u][0] = adj[u][0];
        best[u][1] = adj[u].size() > 1 ? adj[u][1] : -1;
    }

    // Build next[cur][prev]
    for (int cur = 0; cur < N; ++cur) {
        for (int prev = 0; prev < N; ++prev) {
            if (best[cur][0] != prev)
                nxt[cur][prev] = best[cur][0];
            else if (best[cur][1] != -1)
                nxt[cur][prev] = best[cur][1];
            else
                nxt[cur][prev] = prev;
        }
    }

    // Base case: dp[0][cur][prev] = 1 if next move ends at P
    for (int cur = 0; cur < N; ++cur) {
        for (int prev = 0; prev < N; ++prev) {
            int next = nxt[cur][prev];
            if (next == P) dp[0][cur][prev] = 1;
        }
    }

    // Binary lifting
    for (int k = 1; k < LOG; ++k) {
        for (int cur = 0; cur < N; ++cur) {
            for (int prev = 0; prev < N; ++prev) {
                int mid = nxt[cur][prev];
                int nxtp = nxt[mid][cur];
                dp[k][cur][prev] = dp[k-1][mid][cur] + dp[k-1][cur][prev]; // or use mod if needed
                nxt[cur][prev] = nxt[nxt[cur][prev]][cur];
            }
        }
    }

    // Answer queries
    for (int i = 0; i < q; ++i) {
        int K = G[i];
        long long res = 0;

        for (int start = 0; start < N; ++start) {
            for (int to : adj[start]) {
                int cur = to, prev = start;
                long long cnt = 1;
                for (int k = 0; k < LOG; ++k) {
                    if ((K >> k) & 1) {
                        cnt = dp[k][cur][prev];
                        tie(cur, prev) = make_pair(nxt[cur][prev], cur);
                    }
                }
                if (cur == P) res += cnt;
            }
        }

        answer(res);
    }
}

Compilation message (stderr)

/tmp/cciQLKik.o: in function `read_input()':
grader.cpp:(.text+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x12): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x36): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x3d): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x73): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x85): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0x9c): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0xa3): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0xc8): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text+0xde): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status