oj.uz

Submission #790887

# Submission time Handle Problem Language Result Execution time Memory
790887 2023-07-23T09:15:27 Z That_Salamander Tropical Garden (IOI11_garden) C++17
49 / 100
 82 ms 28248 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13320 KB Output is correct
2 Correct 7 ms 13328 KB Output is correct
3 Correct 6 ms 13332 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 6 ms 13232 KB Output is correct
6 Correct 6 ms 13332 KB Output is correct
7 Correct 6 ms 13268 KB Output is correct
8 Correct 6 ms 13268 KB Output is correct
9 Correct 8 ms 13516 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13320 KB Output is correct
2 Correct 7 ms 13328 KB Output is correct
3 Correct 6 ms 13332 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 6 ms 13232 KB Output is correct
6 Correct 6 ms 13332 KB Output is correct
7 Correct 6 ms 13268 KB Output is correct
8 Correct 6 ms 13268 KB Output is correct
9 Correct 8 ms 13516 KB Output is correct
10 Correct 5 ms 13140 KB Output is correct
11 Correct 15 ms 15624 KB Output is correct
12 Correct 26 ms 17492 KB Output is correct
13 Correct 44 ms 25312 KB Output is correct
14 Correct 72 ms 27008 KB Output is correct
15 Correct 82 ms 28248 KB Output is correct
16 Correct 65 ms 24804 KB Output is correct
17 Incorrect 59 ms 24032 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13320 KB Output is correct
2 Correct 7 ms 13328 KB Output is correct
3 Correct 6 ms 13332 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 6 ms 13232 KB Output is correct
6 Correct 6 ms 13332 KB Output is correct
7 Correct 6 ms 13268 KB Output is correct
8 Correct 6 ms 13268 KB Output is correct
9 Correct 8 ms 13516 KB Output is correct
10 Correct 5 ms 13140 KB Output is correct
11 Correct 15 ms 15624 KB Output is correct
12 Correct 26 ms 17492 KB Output is correct
13 Correct 44 ms 25312 KB Output is correct
14 Correct 72 ms 27008 KB Output is correct
15 Correct 82 ms 28248 KB Output is correct
16 Correct 65 ms 24804 KB Output is correct
17 Incorrect 59 ms 24032 KB Output isn't correct
18 Halted 0 ms 0 KB -