oj.uz

Submission #791008

# Submission time Handle Problem Language Result Execution time Memory
791008 2023-07-23T10:52:12 Z That_Salamander Tropical Garden (IOI11_garden) C++17
49 / 100
 117 ms 58032 KB 
#include <bits/stdc++.h>
#define int long long

#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(int32_t x);

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

int visitedA[600000], visitedB[600000];

void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t 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());

        if (conn[i].size() == 0) {
            jump[i*2] = jump[i*2+1] = -1;
            continue;
        }

        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) {
        if (jump[i] == -1) continue;
        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});
        }
    }

    if (period == 0) {
        period = n * 4;
    }

    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]]);
    }
}

//#define ORAC

#ifdef ORAC
void answer(int32_t x) {
    //cout << "ANSWER: " << x << endl;
    cout << x << endl;
}

int32_t R[150000][2];

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

    #ifndef LOCAL_TEST
    freopen("garden.in", "r", stdin);
    freopen("garden.out", "w", stdout);
    #endif

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

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

    int q;
    //cin >> q;

    vector<int32_t> G(q);

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

    //Randomize
    n = 150000;
    m = 150000;

    FOR(i, m) {
        R[i][0] = rand() % n;
        R[i][1] = rand() % n;
    }

    p = rand() % n;

    q = 2000;
    G.resize(q);

    FOR(i, q) {
        G[i] = (rand() * RAND_MAX + rand()) % 1000000000;
    }

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

Compilation message

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37952 KB Output is correct
2 Correct 19 ms 38004 KB Output is correct
3 Correct 19 ms 37988 KB Output is correct
4 Correct 18 ms 37808 KB Output is correct
5 Correct 18 ms 37896 KB Output is correct
6 Correct 20 ms 38148 KB Output is correct
7 Correct 18 ms 37932 KB Output is correct
8 Correct 19 ms 38040 KB Output is correct
9 Correct 20 ms 38484 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37952 KB Output is correct
2 Correct 19 ms 38004 KB Output is correct
3 Correct 19 ms 37988 KB Output is correct
4 Correct 18 ms 37808 KB Output is correct
5 Correct 18 ms 37896 KB Output is correct
6 Correct 20 ms 38148 KB Output is correct
7 Correct 18 ms 37932 KB Output is correct
8 Correct 19 ms 38040 KB Output is correct
9 Correct 20 ms 38484 KB Output is correct
10 Correct 18 ms 37844 KB Output is correct
11 Correct 27 ms 40916 KB Output is correct
12 Correct 39 ms 43480 KB Output is correct
13 Correct 55 ms 53720 KB Output is correct
14 Correct 88 ms 55628 KB Output is correct
15 Correct 117 ms 58032 KB Output is correct
16 Correct 91 ms 53448 KB Output is correct
17 Incorrect 87 ms 52744 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37952 KB Output is correct
2 Correct 19 ms 38004 KB Output is correct
3 Correct 19 ms 37988 KB Output is correct
4 Correct 18 ms 37808 KB Output is correct
5 Correct 18 ms 37896 KB Output is correct
6 Correct 20 ms 38148 KB Output is correct
7 Correct 18 ms 37932 KB Output is correct
8 Correct 19 ms 38040 KB Output is correct
9 Correct 20 ms 38484 KB Output is correct
10 Correct 18 ms 37844 KB Output is correct
11 Correct 27 ms 40916 KB Output is correct
12 Correct 39 ms 43480 KB Output is correct
13 Correct 55 ms 53720 KB Output is correct
14 Correct 88 ms 55628 KB Output is correct
15 Correct 117 ms 58032 KB Output is correct
16 Correct 91 ms 53448 KB Output is correct
17 Incorrect 87 ms 52744 KB Output isn't correct
18 Halted 0 ms 0 KB -