답안 #934130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934130 2024-02-26T20:41:07 Z bobbilyking Regions (IOI09_regions) C++17
0 / 100
60 ms 25064 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 = 300;
// const ll HEAVYTH = 1;
const ll AMT = NN / HEAVYTH + 2;
const ll RR = 2.5e4 + 1;

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);
    
    while (q--) {
        G(r1) G(r2)
        assert(r1 != r2); // i mean this is easily fixable but i dont wanna + its not well defined 

        // 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 {
            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 << ans << '\n';
            for (auto x: people[r2]) seg::modify(tin[x], 0);
        // }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 10584 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 10580 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 10584 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 10840 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 11096 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 10960 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 11352 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 11808 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 11352 KB Time limit exceeded (wall clock)
14 Execution timed out 7 ms 11864 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 13780 KB Time limit exceeded (wall clock)
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 24 ms 14352 KB Time limit exceeded (wall clock)
2 Execution timed out 20 ms 13292 KB Time limit exceeded (wall clock)
3 Execution timed out 23 ms 15368 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 12000 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 13208 KB Time limit exceeded (wall clock)
6 Execution timed out 14 ms 12936 KB Time limit exceeded (wall clock)
7 Execution timed out 16 ms 13580 KB Time limit exceeded (wall clock)
8 Execution timed out 22 ms 17244 KB Time limit exceeded (wall clock)
9 Execution timed out 48 ms 18016 KB Time limit exceeded (wall clock)
10 Execution timed out 38 ms 21008 KB Time limit exceeded (wall clock)
11 Execution timed out 54 ms 17408 KB Time limit exceeded (wall clock)
12 Execution timed out 59 ms 18960 KB Time limit exceeded (wall clock)
13 Execution timed out 46 ms 18980 KB Time limit exceeded (wall clock)
14 Execution timed out 60 ms 18520 KB Time limit exceeded (wall clock)
15 Execution timed out 49 ms 21780 KB Time limit exceeded (wall clock)
16 Execution timed out 48 ms 25064 KB Time limit exceeded (wall clock)
17 Execution timed out 58 ms 24484 KB Time limit exceeded (wall clock)