oj.uz

Submission #178697

# Submission time Handle Problem Language Result Execution time Memory
178697 2020-01-08T08:22:05 Z tri Tropical Garden (IOI11_garden) C++14
100 / 100
 193 ms 40352 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 3e5 + 100;

vector<pi> aL[MAXN];

pi maxI[MAXN];

int nxt[MAXN];

int vis[MAXN];
pi res[MAXN];

int cTime = 1;
int cTar;

vi cPath;

map<int, map<int, vi>> modGroups;

void search(int cV) {
    vis[cV] = cTime;
    cPath.pb(cV);

    int nV = nxt[cV];
    if (vis[nV] == cTime) {
        // cycle found

        int iTar = -1;

        int i;
        for (i = cPath.size() - 1; i >= 0; i--) {
            if (cPath[i] == cTar) {
                iTar = i;
            }
            if (cPath[i] == nV) {
                break;
            }
        }
//
//        ps(cPath);
//        ps(cV, iTar, i);

        int cycleLen = cPath.size() - 1 - i + 1;

        if (iTar != -1) {
            for (i = cPath.size() - 1; i >= 0; i--) {
                int cycleV = cPath[i];
                res[cycleV] = {cycleLen, (iTar - i + cycleLen) % cycleLen};
                if (cPath[i] == nV) {
                    break;
                }
            }
        }

        return;
    }

    if (vis[nV] == 0) {
        search(nxt[cV]);
    }

    if (res[cV].f != -1) { // assigned a value due to cycling behavior
        return;
    }

    pi nRes = res[nV];

    if (nRes.f == -1) {
        if (cV == cTar) {
            res[cV] = {1e9, 0};
        }
        return;
    }
    res[cV] = {nRes.f, nRes.s + 1};
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {

    for (int i = 0; i < M; i++) {
        aL[R[i][0]].pb({R[i][1], M - i});
        aL[R[i][1]].pb({R[i][0], M - i});
    }

    memset(maxI, 0, sizeof(maxI));

    for (int cV = 0; cV < N; cV++) {
        for (pi aE : aL[cV]) {
            maxI[cV] = max(maxI[cV], {aE.s, aE.f});
        }
    }

    for (int cV = 0; cV < N; cV++) {
        assert (aL[cV].size() != 0);

        if (aL[cV].size() == 1) {
            int aV = aL[cV][0].f;
//            if (cV == 4) {
//                ps(aV);
//            }
            if (maxI[cV].f == maxI[aV].f) {
                nxt[cV] = aV + N;
                nxt[cV + N] = aV + N;
            } else {
                nxt[cV] = aV;
                nxt[cV + N] = aV;
            }
            continue;
        }


        pi secMaxI = {-1, -1};

        for (pi aE : aL[cV]) {
            if (aE.s != maxI[cV].f) {
                secMaxI = max(secMaxI, {aE.s, aE.f});
            }
        }

        int aV = maxI[cV].s;
        if (maxI[aV].f == maxI[cV].f) {
            nxt[cV] = aV + N;
        } else {
            nxt[cV] = aV;
        }

        aV = secMaxI.s;
        if (maxI[aV].f == secMaxI.f) {
            nxt[cV + N] = aV + N;
        } else {
            nxt[cV + N] = aV;
        }
    }



//    ps("nxts");
//    for (int i = 0; i < 2 * N; i++) {
//        ps(nxt[i]);
//    }
//    ps("endsnxts");


    for (int phase = 0; phase < 2; phase++) {
        for (int i = 0; i < 2 * N; i++) {
            vis[i] = 0;
            res[i] = {-1, -1};
        }
        cTime = 1;
        cTar = P + N * phase;

        for (int i = 0; i < 2 * N; i++) {
            if (!vis[i]) {
                cPath.clear();
                search(i);
                cTime++;
            }
        }

//        ps("phase print");
//
//        for (int i = 0; i < 2 * N; i++) {
//            ps(res[i]);
//        }
//
//        ps("complete phase");

        for (int i = 0; i < N; i++) {
            if (res[i].f != -1) {
                int cycleLen = res[i].f;
                map<int, vi> &cGroup = modGroups[cycleLen];
                cGroup[res[i].s % cycleLen].pb(res[i].s);
            }
        }
    }

//
//    ps("Q:", Q);
//    ps();

    for (auto &x: modGroups) {
        for (auto &y : x.s) {
            auto &z = y.s;
            sort(z.begin(), z.end());
//            ps(x.f, y.f);
//            ps(z);
        }
    }

    for (int cQ = 0; cQ < Q; cQ++) {
        int K = G[cQ];
        int sum = 0;
        for (auto &x : modGroups) {
            map<int, vi> &cGroup = x.s;
            int rem = K % x.f;

            vi &vals = cGroup[rem];

            sum += upper_bound(vals.begin(), vals.end(), K) - vals.begin();
        }
        answer(sum);
//        ps(sum);
    }

//    for (auto &x : modGroups) {
//        vi &cGroup = x.s;
//        if (x.f != 1e6) {
//            ps(x.f);
//            ps(cGroup);
//        }
//    }

}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9892 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 11 ms 9788 KB Output is correct
4 Correct 10 ms 9692 KB Output is correct
5 Correct 12 ms 9804 KB Output is correct
6 Correct 13 ms 9848 KB Output is correct
7 Correct 13 ms 9820 KB Output is correct
8 Correct 13 ms 9848 KB Output is correct
9 Correct 13 ms 10104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9892 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 11 ms 9788 KB Output is correct
4 Correct 10 ms 9692 KB Output is correct
5 Correct 12 ms 9804 KB Output is correct
6 Correct 13 ms 9848 KB Output is correct
7 Correct 13 ms 9820 KB Output is correct
8 Correct 13 ms 9848 KB Output is correct
9 Correct 13 ms 10104 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 23 ms 11760 KB Output is correct
12 Correct 38 ms 13432 KB Output is correct
13 Correct 111 ms 33736 KB Output is correct
14 Correct 105 ms 20536 KB Output is correct
15 Correct 117 ms 21340 KB Output is correct
16 Correct 118 ms 19552 KB Output is correct
17 Correct 93 ms 18220 KB Output is correct
18 Correct 33 ms 13212 KB Output is correct
19 Correct 103 ms 20428 KB Output is correct
20 Correct 122 ms 21376 KB Output is correct
21 Correct 106 ms 19036 KB Output is correct
22 Correct 102 ms 18024 KB Output is correct
23 Correct 110 ms 21756 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9892 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 11 ms 9788 KB Output is correct
4 Correct 10 ms 9692 KB Output is correct
5 Correct 12 ms 9804 KB Output is correct
6 Correct 13 ms 9848 KB Output is correct
7 Correct 13 ms 9820 KB Output is correct
8 Correct 13 ms 9848 KB Output is correct
9 Correct 13 ms 10104 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 23 ms 11760 KB Output is correct
12 Correct 38 ms 13432 KB Output is correct
13 Correct 111 ms 33736 KB Output is correct
14 Correct 105 ms 20536 KB Output is correct
15 Correct 117 ms 21340 KB Output is correct
16 Correct 118 ms 19552 KB Output is correct
17 Correct 93 ms 18220 KB Output is correct
18 Correct 33 ms 13212 KB Output is correct
19 Correct 103 ms 20428 KB Output is correct
20 Correct 122 ms 21376 KB Output is correct
21 Correct 106 ms 19036 KB Output is correct
22 Correct 102 ms 18024 KB Output is correct
23 Correct 110 ms 21756 KB Output is correct
24 Correct 11 ms 9720 KB Output is correct
25 Correct 23 ms 11896 KB Output is correct
26 Correct 39 ms 13432 KB Output is correct
27 Correct 112 ms 33768 KB Output is correct
28 Correct 115 ms 20484 KB Output is correct
29 Correct 125 ms 21460 KB Output is correct
30 Correct 116 ms 19400 KB Output is correct
31 Correct 97 ms 18268 KB Output is correct
32 Correct 48 ms 13276 KB Output is correct
33 Correct 105 ms 20512 KB Output is correct
34 Correct 120 ms 21388 KB Output is correct
35 Correct 112 ms 18960 KB Output is correct
36 Correct 104 ms 18208 KB Output is correct
37 Correct 115 ms 21716 KB Output is correct
38 Correct 193 ms 40352 KB Output is correct