oj.uz

Submission #196580

# Submission time Handle Problem Language Result Execution time Memory
196580 2020-01-17T04:40:20 Z tri Regions (IOI09_regions) C++14
100 / 100
 7352 ms 39316 KB 
#include <bits/stdc++.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 = 2e5 + 100;
const int SQRTN = 400; // slightly smaller as smaller groups have extra lg factor

int N, R, Q;

int color[MAXN], par[MAXN];
vi aL[MAXN];

vi mems[MAXN];
vi locs[MAXN];

int tSt[MAXN], tEnd[MAXN];
int cT = 0;

void dfs(int cV) {
    tSt[cV] = cT++;
    for (int aV : aL[cV]) {
        dfs(aV);
    }
    tEnd[cV] = cT - 1;
}

vi bigC;
int cMap[MAXN];

int actCnt[MAXN];
int cCnt[MAXN / SQRTN + 10][MAXN];

void dfs2(int cV) {
    for (int cBigC : bigC) {
        cCnt[cMap[cBigC]][color[cV]] += actCnt[cBigC];
    }

    actCnt[color[cV]]++;

    for (int aV : aL[cV]) {
        dfs2(aV);
    }

    actCnt[color[cV]]--;
}

int main() {
    cin >> N >> R >> Q;

    cin >> color[0];
    color[0]--;
    for (int cV = 1; cV < N; cV++) {
        cin >> par[cV] >> color[cV];
        par[cV]--, color[cV]--;
        aL[par[cV]].pb(cV);
    }

    dfs(0);

//    for (int i = 0; i < N; i++) {
//        pr(tSt[i], " ");
//    }
//    ps();

    for (int cV = 0; cV < N; cV++) {
        mems[color[cV]].pb(cV);
        locs[color[cV]].pb(tSt[cV]);
    }

    fill(cMap, cMap + MAXN, -1);
    for (int cC = 0; cC < N; cC++) {
        sort(locs[cC].begin(), locs[cC].end());
        if (mems[cC].size() > SQRTN) {
            cMap[cC] = bigC.size();
            bigC.pb(cC);
        }
    }

    dfs2(0);

    for (int cQ = 0; cQ < Q; cQ++) {
        int cAnc, cDes;
        cin >> cAnc >> cDes;
        cAnc--, cDes--;

        int ans = 0;
        if (mems[cAnc].size() <= SQRTN) {
//            ps(locs[cDes]);
            for (int cV : mems[cAnc]) {
                int cTSt = tSt[cV];
                int cTEnd = tEnd[cV];

//                ps(cV, cTSt, cTEnd);

                auto r = upper_bound(locs[cDes].begin(), locs[cDes].end(), cTEnd);
                auto l = upper_bound(locs[cDes].begin(), locs[cDes].end(), cTSt); // exclude cTSt

                ans += r - l;
            }
        } else {
            int mapped = cMap[cAnc];
            ans = cCnt[mapped][cDes];
        }
//        ps("ans");
        cout << ans << endl;
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15216 KB Output is correct
2 Correct 16 ms 15224 KB Output is correct
3 Correct 19 ms 15224 KB Output is correct
4 Correct 21 ms 15224 KB Output is correct
5 Correct 23 ms 15224 KB Output is correct
6 Correct 35 ms 15352 KB Output is correct
7 Correct 42 ms 15220 KB Output is correct
8 Correct 56 ms 15352 KB Output is correct
9 Correct 68 ms 15724 KB Output is correct
10 Correct 90 ms 15832 KB Output is correct
11 Correct 147 ms 16168 KB Output is correct
12 Correct 179 ms 16452 KB Output is correct
13 Correct 233 ms 16248 KB Output is correct
14 Correct 439 ms 16888 KB Output is correct
15 Correct 423 ms 18936 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2267 ms 20044 KB Output is correct
2 Correct 2889 ms 19044 KB Output is correct
3 Correct 3600 ms 21492 KB Output is correct
4 Correct 321 ms 16936 KB Output is correct
5 Correct 443 ms 18188 KB Output is correct
6 Correct 695 ms 20356 KB Output is correct
7 Correct 1950 ms 20780 KB Output is correct
8 Correct 1443 ms 27944 KB Output is correct
9 Correct 3356 ms 24968 KB Output is correct
10 Correct 4331 ms 39316 KB Output is correct
11 Correct 7352 ms 25312 KB Output is correct
12 Correct 2313 ms 26680 KB Output is correct
13 Correct 3097 ms 26768 KB Output is correct
14 Correct 3318 ms 28428 KB Output is correct
15 Correct 4597 ms 30356 KB Output is correct
16 Correct 4508 ms 33576 KB Output is correct
17 Correct 4223 ms 34540 KB Output is correct