oj.uz

Submission #474701

# Submission time Handle Problem Language Result Execution time Memory
474701 2021-09-19T12:48:39 Z hidden1 Tropical Garden (IOI11_garden) C++14
100 / 100
 194 ms 76868 KB 
#include "gardenlib.h"
#include "garden.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const int MAX_N = 4e5 + 10;
vector<int> g[MAX_N];
vector<int> help[MAX_N];
int n, par[MAX_N], mn[MAX_N];
int cnt[2];
vector<int> ans[2][MAX_N];
int used[MAX_N];
int d[2][MAX_N];

void dfs(int x, int who) {
    if(x < n) {
        ans[who][d[who][x]].push_back(d[who][x]);
    }
    used[x] = true;
    for(auto it : g[x]) {
        if(used[it]) {cnt[who] = d[who][x] - d[who][it] + 1; continue;}
        d[who][it] = d[who][x] + 1;
        dfs(it, who);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N;
    fill_n(mn, n, 1e8);
    for(int i = 0; i < M; i ++) {
        int a = R[i][0], b = R[i][1];
        help[a].push_back(i);
        help[b].push_back(i);
        chkmin(mn[a], i);
        chkmin(mn[b], i);
    }
    for(int i = 0; i < n; i ++) {
        sort(help[i].begin(), help[i].end());
        if(help[i].size() == 0) {
            continue;
        } else {
            // ???
            int best = help[i][0];
            par[i] = R[best][0] + R[best][1] - i;
            if(mn[par[i]] == best) {
                par[i] += n;
            }
            best = help[i][1 % help[i].size()];
            par[i + n] = R[best][0] + R[best][1] - i;
            if(mn[par[i + n]] == best) {
                par[i + n] += n;
            }
        }
    }
    for(int i = 0; i < 2 * n; i ++) {
        g[par[i]].push_back(i);
    }

    cnt[0] = cnt[1] = -1;
    fill_n(used, 2 * n, 0);
    dfs(P, 0);

    fill_n(used, 2 * n, 0);
    dfs(P + n, 1);

    for(int i = 0; i < 2; i ++) {
        if(cnt[i] == -1) {continue;}
        for(int j = cnt[i]; j < MAX_N; j ++) {
            for(auto it : ans[i][j]) {
                ans[i][it % cnt[i]].push_back(it);
            }
        }
    }

    for(int i = 0; i < Q; i ++) {
        int ret = 0;
        if(cnt[0] != -1) {
            ret += upper_bound(ans[0][G[i] % cnt[0]].begin(), ans[0][G[i] % cnt[0]].end(), G[i]) - ans[0][G[i] % cnt[0]].begin();
        } else {
            if(G[i] < MAX_N) {
                ret += ans[0][G[i]].size();
            }
        }

        if(cnt[1] != -1) {
            ret += upper_bound(ans[1][G[i] % cnt[1]].begin(), ans[1][G[i] % cnt[1]].end(), G[i]) - ans[1][G[i] % cnt[1]].begin();
        } else {
            if(G[i] < MAX_N) {
                ret += ans[1][G[i]].size();
            }
        }

        answer(ret);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38220 KB Output is correct
2 Correct 25 ms 38020 KB Output is correct
3 Correct 25 ms 38084 KB Output is correct
4 Correct 23 ms 37868 KB Output is correct
5 Correct 24 ms 37828 KB Output is correct
6 Correct 25 ms 38244 KB Output is correct
7 Correct 24 ms 37836 KB Output is correct
8 Correct 25 ms 37924 KB Output is correct
9 Correct 27 ms 38176 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38220 KB Output is correct
2 Correct 25 ms 38020 KB Output is correct
3 Correct 25 ms 38084 KB Output is correct
4 Correct 23 ms 37868 KB Output is correct
5 Correct 24 ms 37828 KB Output is correct
6 Correct 25 ms 38244 KB Output is correct
7 Correct 24 ms 37836 KB Output is correct
8 Correct 25 ms 37924 KB Output is correct
9 Correct 27 ms 38176 KB Output is correct
10 Correct 23 ms 37864 KB Output is correct
11 Correct 35 ms 40412 KB Output is correct
12 Correct 54 ms 41936 KB Output is correct
13 Correct 86 ms 68192 KB Output is correct
14 Correct 137 ms 53828 KB Output is correct
15 Correct 158 ms 55620 KB Output is correct
16 Correct 129 ms 50396 KB Output is correct
17 Correct 139 ms 49328 KB Output is correct
18 Correct 57 ms 42564 KB Output is correct
19 Correct 144 ms 54520 KB Output is correct
20 Correct 189 ms 55872 KB Output is correct
21 Correct 128 ms 50116 KB Output is correct
22 Correct 113 ms 49348 KB Output is correct
23 Correct 132 ms 54924 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38220 KB Output is correct
2 Correct 25 ms 38020 KB Output is correct
3 Correct 25 ms 38084 KB Output is correct
4 Correct 23 ms 37868 KB Output is correct
5 Correct 24 ms 37828 KB Output is correct
6 Correct 25 ms 38244 KB Output is correct
7 Correct 24 ms 37836 KB Output is correct
8 Correct 25 ms 37924 KB Output is correct
9 Correct 27 ms 38176 KB Output is correct
10 Correct 23 ms 37864 KB Output is correct
11 Correct 35 ms 40412 KB Output is correct
12 Correct 54 ms 41936 KB Output is correct
13 Correct 86 ms 68192 KB Output is correct
14 Correct 137 ms 53828 KB Output is correct
15 Correct 158 ms 55620 KB Output is correct
16 Correct 129 ms 50396 KB Output is correct
17 Correct 139 ms 49328 KB Output is correct
18 Correct 57 ms 42564 KB Output is correct
19 Correct 144 ms 54520 KB Output is correct
20 Correct 189 ms 55872 KB Output is correct
21 Correct 128 ms 50116 KB Output is correct
22 Correct 113 ms 49348 KB Output is correct
23 Correct 132 ms 54924 KB Output is correct
24 Correct 24 ms 37892 KB Output is correct
25 Correct 38 ms 40680 KB Output is correct
26 Correct 55 ms 42636 KB Output is correct
27 Correct 91 ms 69164 KB Output is correct
28 Correct 125 ms 54508 KB Output is correct
29 Correct 194 ms 55628 KB Output is correct
30 Correct 147 ms 50520 KB Output is correct
31 Correct 123 ms 49324 KB Output is correct
32 Correct 59 ms 42528 KB Output is correct
33 Correct 142 ms 54344 KB Output is correct
34 Correct 175 ms 55688 KB Output is correct
35 Correct 129 ms 50784 KB Output is correct
36 Correct 123 ms 49592 KB Output is correct
37 Correct 181 ms 55024 KB Output is correct
38 Correct 165 ms 76868 KB Output is correct