oj.uz

Submission #834894

# Submission time Handle Problem Language Result Execution time Memory
834894 2023-08-22T22:54:51 Z Magikarp4000 Tropical Garden (IOI11_garden) C++17
100 / 100
 132 ms 48456 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 3e5+10;
int n,m,tgt,q;
vector<PII> adj[MAXN];
int f[MAXN], pos[2], d[MAXN][2], cnt[MAXN][2], start[2], len[2];
int res[MAXN], rogue[MAXN];
vector<int> r[MAXN];
bool z[MAXN][2], cyc[MAXN][2], z1[MAXN][2];

int dfs(int s, int idx) {
    int num = 0;
    while (!z[s][idx]) {
        z[s][idx] = 1;
        s = f[s];
        num++;
    }
    return s;
}

int dfs1(int s, int idx) {
    bool begun = 0;
    int num = 0;
    while (!begun || s != start[idx]) {
        begun = 1;
        if (s == tgt) pos[0] = num;
        else if (s == tgt+n) pos[1] = num;
        cyc[s][idx] = 1;
        num++;
        s = f[s];
    }
    return num;
}

void dfs2(int s, int idx) {
    if (pos[idx] == -1) return;
    bool begun = 0;
    int num = 0;
    while (!begun || s != start[idx]) {
        begun = 1;
        d[s][idx] = pos[idx] >= num ? pos[idx]-num : pos[idx]-num+len[idx];
        num++;
        s = f[s];
    }
}

void dfs3(int s, int idx) {
    if (pos[idx] == -1) return;
    stack<int> st;
    while (d[s][idx] == -1) {
        st.push(s);
        s = f[s];
    }
    int num = d[s][idx]+1;
    while (!st.empty()) {
        int cur = st.top();
        st.pop();
        d[cur][idx] = num++;
    }
}

void dfs4(int s, int dist) {
    if (s < n) rogue[dist]++;
    FORX(u,r[s]) dfs4(u,dist+1);
}

void dfs5(int s, int idx) {
    if (z1[s][idx]) return;
    z1[s][idx] = 1;
    FORX(u,r[s]) dfs5(u,idx);
    dfs5(f[s],idx);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N, m = M, tgt = P, q = Q;
    FOR(i,0,m) {
        int a = R[i][0], b = R[i][1];
        adj[a].PB({i,b});
        adj[b].PB({i,a});
    }
    FOR(i,0,n) sort(ALL(adj[i]));
    FOR(i,0,n) {
        int best = adj[i][0].S;
        if (adj[best][0].S == i) f[i] = best+n;
        else f[i] = best;
        int best1 = adj[i].size() <= 1 ? best : adj[i][1].S;
        if (adj[best1][0].S == i) f[i+n] = best1+n;
        else f[i+n] = best1;
    }
    FOR(i,0,n*2) r[f[i]].PB(i);
    FOR(i,0,n*2) {
        FOR(j,0,2) d[i][j] = -1;
    }
    pos[0] = pos[1] = -1;
    len[0] = len[1] = 1;
    FOR(j,0,2) {
        int cur = j == 0 ? tgt : tgt+n;
        dfs5(cur,j);
        start[j] = dfs(cur,j);
        len[j] = dfs1(start[j],j);
        dfs2(start[j],j);
        FOR(i,0,n*2) if (z1[i][j]) dfs3(i,j);
        if (!cyc[cur][j]) dfs4(cur,0);
    }
    vector<int> val[2];
    FOR(j,0,2) {
        FOR(i,0,n) {
            if (d[i][j] != -1) {
                val[j].PB(d[i][j]);
                cnt[d[i][j]%len[j]][j]++;
            }
        }
        sort(ALL(val[j]), greater<int>());
    }
    int v0n = val[0].size(), v1n = val[1].size();
    vector<PII> qrs;
    FOR(i,0,q) qrs.PB({G[i],i});
    sort(ALL(qrs), greater<PII>());
    int j = 0, k = 0;
    FOR(i,0,q) {
        int x = qrs[i].F, idx = qrs[i].S;
        while (j < v0n && val[0][j] > x) cnt[val[0][j++]%len[0]][0]--;
        while (k < v1n && val[1][k] > x) cnt[val[1][k++]%len[1]][1]--;
        int extra = x >= MAXN ? 0 : rogue[x];
        res[idx] = cnt[x%len[0]][0]+cnt[x%len[1]][1]+extra;
    }
    FOR(i,0,q) answer(res[i]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 15 ms 17236 KB Output is correct
12 Correct 25 ms 19476 KB Output is correct
13 Correct 60 ms 39496 KB Output is correct
14 Correct 72 ms 30800 KB Output is correct
15 Correct 100 ms 32156 KB Output is correct
16 Correct 107 ms 28072 KB Output is correct
17 Correct 74 ms 26676 KB Output is correct
18 Correct 29 ms 19540 KB Output is correct
19 Correct 73 ms 30796 KB Output is correct
20 Correct 114 ms 31812 KB Output is correct
21 Correct 102 ms 28008 KB Output is correct
22 Correct 75 ms 26572 KB Output is correct
23 Correct 71 ms 32232 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 8 ms 14548 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14804 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 15 ms 17236 KB Output is correct
12 Correct 25 ms 19476 KB Output is correct
13 Correct 60 ms 39496 KB Output is correct
14 Correct 72 ms 30800 KB Output is correct
15 Correct 100 ms 32156 KB Output is correct
16 Correct 107 ms 28072 KB Output is correct
17 Correct 74 ms 26676 KB Output is correct
18 Correct 29 ms 19540 KB Output is correct
19 Correct 73 ms 30796 KB Output is correct
20 Correct 114 ms 31812 KB Output is correct
21 Correct 102 ms 28008 KB Output is correct
22 Correct 75 ms 26572 KB Output is correct
23 Correct 71 ms 32232 KB Output is correct
24 Correct 7 ms 14420 KB Output is correct
25 Correct 15 ms 17364 KB Output is correct
26 Correct 29 ms 19672 KB Output is correct
27 Correct 61 ms 39496 KB Output is correct
28 Correct 77 ms 30796 KB Output is correct
29 Correct 112 ms 31660 KB Output is correct
30 Correct 74 ms 28112 KB Output is correct
31 Correct 73 ms 26796 KB Output is correct
32 Correct 30 ms 19532 KB Output is correct
33 Correct 72 ms 30796 KB Output is correct
34 Correct 132 ms 32076 KB Output is correct
35 Correct 97 ms 28064 KB Output is correct
36 Correct 79 ms 26696 KB Output is correct
37 Correct 75 ms 32292 KB Output is correct
38 Correct 96 ms 48456 KB Output is correct