Submission #790887

#	Time	Username	Problem	Language	Result	Execution time	Memory
790887		That_Salamander	Tropical Garden (IOI11_garden)	C++17	49 / 100	82 ms	28248 KiB

garden

#include <bits/stdc++.h>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void answer(int x);

int n, m, p;
vector<pii> conn[150000];
int jump[300000];
vi back[300000];

int visitedA[300000], visitedB[300000];

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

    FOR(i, m) {
        conn[R[i][0]].push_back({i, R[i][1]});
        conn[R[i][1]].push_back({i, R[i][0]});
    }

    FOR(i, n) {
        sort(conn[i].begin(), conn[i].end());
    }

    FOR(i, n) {
        sort(conn[i].begin(), conn[i].end());

        jump[i*2] = conn[i][0].second * 2;
        if (conn[jump[i*2]/2][0].first == conn[i][0].first) {
            jump[i*2]++;
        }

        if (conn[i].size() == 1) {
            jump[i*2+1] = jump[i*2];
        } else {
            jump[i*2+1] = conn[i][1].second * 2;

            if (conn[jump[i*2+1]/2][0].first == conn[i][1].first) {
                jump[i*2+1]++;
            }
        }
    }

    FOR(i, n * 2) {
        back[jump[i]].push_back(i);
    }


    memset(visitedA, -1, sizeof(visitedA));
    memset(visitedB, -1, sizeof(visitedB));
    int period = 0;

    queue<pii> q;

    q.push({p*2, 0});
    while (!q.empty()) {
        auto [x, dist] = q.front(); q.pop();

        if (visitedA[x] == -1) {
            visitedA[x] = dist;
        } else {
            if (period == 0) {
                period = dist - visitedA[x];
            }

            continue;
        }

        for (int c: back[x]) {
            q.push({c, dist + 1});
        }
    }

    q.push({p*2+1, 0});
    while (!q.empty()) {
        auto [x, dist] = q.front(); q.pop();

        if (visitedB[x] == -1) {
            visitedB[x] = dist;
        } else {
            if (period == 0) {
                period = dist - visitedB[x];
            }

            continue;
        }

        for (int c: back[x]) {
            q.push({c, dist + 1});
        }
    }

    vi m(period);

    vi times;

    FOR(i, n) {
        if (visitedA[i*2] != -1) times.push_back(visitedA[i*2]);
        if (visitedB[i*2] != -1) times.push_back(visitedB[i*2]);
    }

    sort(times.begin(), times.end());
    int ti = 0;

    vi gc(Q);
    FOR(i, Q) {
        gc[i] = G[i];
    }

    sort(gc.begin(), gc.end());
    map<int, int> res;

    for (int x: gc) {
        while (ti < times.size() && times[ti] <= x) {
            m[times[ti++] % period]++;
        }

        res[x] = m[x%period];
    }

    FOR(i, Q) {
        //cout << res[g[i]] << " ";
        answer(res[G[i]]);
    }
}


#ifdef LOCAL_TEST
void answer(int x) {
    cout << "ANSWER: " << x << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, p;
    cin >> n >> m >> p;

    vector<int[2]> R(m);

    FOR(i, m) {
        cin >> R[i][0] >> R[i][1];
    }

    int q;
    cin >> q;

    vi G(q);

    FOR(i, q) {
        cin >> G[i];
    }

    count_routes(n, m, p, R.data(), q, G.data());
}
#endif

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         while (ti < times.size() && times[ti] <= x) {
      |                ~~~^~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31