oj.uz

답안 #934165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934165 2024-02-26T22:41:18 Z bobbilyking Regions (IOI09_regions) C++17
30 / 100
 3910 ms 46832 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }




const ll NN = 2e5 + 1;
// const ll NN = 200;
const ll HEAVYTH = 1;
// const ll RR = 2.5e4 + 1;
const ll RR = 500;

const ll AMT = RR / HEAVYTH + 2;

ll label[NN], tin[NN], tout[NN];
vl people[RR];
vl adj[NN];

vl dfsorder;

vl heavies;

void dfsinit(ll i) {
    static int time = 0;
    tin[i] = time++;
    dfsorder.push_back(i);
    for (auto x: adj[i]) dfsinit(x);
    tout[i] = time;
}
/*
bool isPar(ll i, ll j) {
    return tin[i] <= tin[j] and tin[j] < tout[i];
}

ll heavyRoot[AMT][RR];

void solveHeavyRoot(ll ask, ll put) {
    // compute number of ask labels on path to root, add to ans 
    vl stk;
    ll cnt = 0;

    for (auto x: dfsorder) {
        while (stk.size() and !isPar(stk.back(), x)) {
            cnt -= label[stk.back()] == ask;
            stk.pop_back();
        }
        cnt += label[x] == ask;
        stk.push_back(x);

        heavyRoot[put][label[x]] += cnt;

    }
}

ll containsHeavy[AMT][RR];

void solveContainsHeavy(ll ask, ll put) {
    // compute number of ask in subtree, then add to answer 
    vl ans(dfsorder.size() + 1);
    FD(i, ll(dfsorder.size()) - 1, -1) {
        ll x = dfsorder[i];
        for (auto y: adj[x]) ans[x] += ans[y];
        ans[x] += label[x] == ask;
        
        containsHeavy[put][label[x]] += ans[x];
    }
}
*/

namespace seg {
    typedef ll T;
    T id=0;
    T f(T a, T b) {return a+b;}

    T t[2 * NN];
    ll n=NN;  // array size

    void modify(ll p, T value) {  // set value at position p
      for (p+=n, t[p] = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    G(n) G(r) G(q)
    
    cin >> label[1]; people[label[1]].push_back(1);
    F(i, 2, n+1) {
        G(par) cin >> label[i]; 
        adj[par].push_back(i);
        people[label[i]].push_back(i);
    }

    dfsinit(1);

    // F(i, 1, r+1) if (people[i].size() >= HEAVYTH) {
    //     heavies.push_back(i);
    // }

    // F(i, 0, heavies.size()) {
    //     solveHeavyRoot(heavies[i], i);
    // }

    // F(i, 0, heavies.size()) {
    //     solveContainsHeavy(heavies[i], i);
    // }

    // cout << heavies.size() << " vs " << r << endl;

    // exit(0);
    
    map<pl, ll> cache;
    while (q--) {
        G(r1) G(r2)
        assert(r1 != r2); // i mean this is easily fixable but i dont wanna + its not well defined 
        if (cache.count(pl{r1, r2})) {
            cout << cache[{r1, r2}] << endl;
            continue;
        } 
        // if (people[r1].size() >= HEAVYTH) {
        //     cout << heavyRoot[lower_bound(A(heavies), r1) - heavies.begin()][r2] << '\n';
        // } else if (people[r2].size() >= HEAVYTH) {
        //     cout << containsHeavy[lower_bound(A(heavies), r2) - heavies.begin()][r1] << '\n';
        // } else {
            // assert(false);
            for (auto x: people[r2]) seg::modify(tin[x], 1);
            ll ans = 0;
            for (auto x: people[r1]) ans += seg::query(tin[x], tout[x]);
            cout << (cache[{r1, r2}] = ans) << endl;
            for (auto x: people[r2]) seg::modify(tin[x], 0);
        // }
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 4 ms 8956 KB Output is correct
4 Correct 4 ms 8952 KB Output is correct
5 Correct 6 ms 8976 KB Output is correct
6 Correct 12 ms 9048 KB Output is correct
7 Correct 16 ms 10096 KB Output is correct
8 Correct 23 ms 9048 KB Output is correct
9 Correct 40 ms 9640 KB Output is correct
10 Correct 62 ms 10504 KB Output is correct
11 Correct 127 ms 10696 KB Output is correct
12 Correct 151 ms 11188 KB Output is correct
13 Correct 158 ms 10644 KB Output is correct
14 Correct 277 ms 11752 KB Output is correct
15 Correct 501 ms 13224 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1971 ms 14864 KB Output is correct
2 Correct 1793 ms 13948 KB Output is correct
3 Correct 3910 ms 19036 KB Output is correct
4 Runtime error 17 ms 19804 KB Execution killed with signal 11
5 Runtime error 19 ms 22008 KB Execution killed with signal 11
6 Runtime error 23 ms 21640 KB Execution killed with signal 11
7 Runtime error 25 ms 22992 KB Execution killed with signal 11
8 Runtime error 31 ms 30040 KB Execution killed with signal 11
9 Runtime error 61 ms 31068 KB Execution killed with signal 11
10 Runtime error 54 ms 37984 KB Execution killed with signal 11
11 Runtime error 58 ms 30140 KB Execution killed with signal 11
12 Runtime error 72 ms 33916 KB Execution killed with signal 11
13 Runtime error 67 ms 33728 KB Execution killed with signal 11
14 Runtime error 74 ms 33368 KB Execution killed with signal 11
15 Runtime error 63 ms 39568 KB Execution killed with signal 11
16 Runtime error 63 ms 46832 KB Execution killed with signal 11
17 Runtime error 65 ms 44884 KB Execution killed with signal 11