oj.uz

Submission #397251

# Submission time Handle Problem Language Result Execution time Memory
397251 2021-05-01T18:43:11 Z rocks03 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 84516 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXK = 30;
const int MAXN = 2e5+100;
int N, M, P, nxt[2][MAXK][MAXN], wei[2][MAXK][MAXN];
vector<pii> g[MAXN];

void build(){
    rep(i, 0, N){
        sort(all(g[i]));
        while(SZ(g[i]) > 2) g[i].pop_back();
        if(SZ(g[i]) < 2) g[i].pb(g[i][0]);
        nxt[0][0][i] = g[i][0].ss;
        wei[0][0][i] = g[i][0].ff;
        nxt[1][0][i] = g[i][1].ss;
        wei[1][0][i] = g[i][1].ff;
    }
    rep(k, 0, MAXK - 1){
        rep(i, 0, N){
            int u;
            u = nxt[0][k][i];
            nxt[0][k + 1][i] = nxt[0][k][u];
            wei[0][k + 1][i] = wei[0][k][u];
            if(wei[0][k][i] == wei[0][0][u]){
                nxt[0][k + 1][i] = nxt[1][k][u];
                wei[0][k + 1][i] = wei[1][k][u];
            }
            u = nxt[1][k][i];
            nxt[1][k + 1][i] = nxt[0][k][u];
            wei[1][k + 1][i] = wei[0][k][u];
            if(wei[1][k][i] == wei[0][0][u]){
                nxt[1][k + 1][i] = nxt[1][k][u];
                wei[1][k + 1][i] = wei[1][k][u];
            }
        }
    }
}

int jump(int v, int K){
    int w = -1;
    per(k, MAXK - 1, 0){
        if(K >> k & 1){
            if(wei[0][0][v] != w){
                w = wei[0][k][v];
                v = nxt[0][k][v];
            } else{
                w = wei[1][k][v];
                v = nxt[1][k][v];
            }
        }
    }
    return v;
}

int query(int K){
    int ans = 0;
    rep(i, 0, N){
        if(jump(i, K) == P)
            ans++;
    }
    return ans;
}

void answer(int x);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    :: N = N, ::M = M, ::P = P;
    rep(m, 0, M){
        int u = R[m][0], v = R[m][1];
        g[u].pb({m, v});
        g[v].pb({m, u});
    }
    build();
    rep(q, 0, Q){
        answer(query(G[q]));
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 6172 KB Output is correct
3 Correct 6 ms 6092 KB Output is correct
4 Correct 4 ms 5712 KB Output is correct
5 Correct 3 ms 5580 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 5 ms 6168 KB Output is correct
9 Correct 7 ms 6432 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 6172 KB Output is correct
3 Correct 6 ms 6092 KB Output is correct
4 Correct 4 ms 5712 KB Output is correct
5 Correct 3 ms 5580 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 5 ms 6168 KB Output is correct
9 Correct 7 ms 6432 KB Output is correct
10 Correct 3 ms 5708 KB Output is correct
11 Correct 23 ms 17356 KB Output is correct
12 Correct 39 ms 26000 KB Output is correct
13 Correct 67 ms 49900 KB Output is correct
14 Correct 122 ms 77000 KB Output is correct
15 Correct 122 ms 77892 KB Output is correct
16 Correct 94 ms 55836 KB Output is correct
17 Correct 106 ms 48740 KB Output is correct
18 Correct 39 ms 25924 KB Output is correct
19 Correct 123 ms 76868 KB Output is correct
20 Correct 134 ms 77940 KB Output is correct
21 Correct 98 ms 55748 KB Output is correct
22 Correct 107 ms 48420 KB Output is correct
23 Correct 130 ms 84516 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 6172 KB Output is correct
3 Correct 6 ms 6092 KB Output is correct
4 Correct 4 ms 5712 KB Output is correct
5 Correct 3 ms 5580 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 5 ms 6168 KB Output is correct
9 Correct 7 ms 6432 KB Output is correct
10 Correct 3 ms 5708 KB Output is correct
11 Correct 23 ms 17356 KB Output is correct
12 Correct 39 ms 26000 KB Output is correct
13 Correct 67 ms 49900 KB Output is correct
14 Correct 122 ms 77000 KB Output is correct
15 Correct 122 ms 77892 KB Output is correct
16 Correct 94 ms 55836 KB Output is correct
17 Correct 106 ms 48740 KB Output is correct
18 Correct 39 ms 25924 KB Output is correct
19 Correct 123 ms 76868 KB Output is correct
20 Correct 134 ms 77940 KB Output is correct
21 Correct 98 ms 55748 KB Output is correct
22 Correct 107 ms 48420 KB Output is correct
23 Correct 130 ms 84516 KB Output is correct
24 Correct 17 ms 5760 KB Output is correct
25 Correct 3598 ms 17464 KB Output is correct
26 Execution timed out 5044 ms 26080 KB Time limit exceeded
27 Halted 0 ms 0 KB -