oj.uz

답안 #934127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934127 2024-02-26T20:25:17 Z bobbilyking Regions (IOI09_regions) C++17
0 / 100
 553 ms 44636 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) {
        solveHeavyRoot(i, heavies.size());
        solveContainsHeavy(i, heavies.size());
        heavies.push_back(i);
    }
    
    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);
        }
    }
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
2 Execution timed out 2 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 2 ms 10584 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 10584 KB Time limit exceeded (wall clock)
6 Execution timed out 5 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 10836 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 11096 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 11096 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 11352 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 11664 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 11372 KB Time limit exceeded (wall clock)
14 Execution timed out 7 ms 11864 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 13524 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 37 ms 20536 KB Time limit exceeded (wall clock)
2 Execution timed out 37 ms 19484 KB Time limit exceeded (wall clock)
3 Execution timed out 25 ms 19664 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 11952 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 12980 KB Time limit exceeded (wall clock)
6 Execution timed out 71 ms 27296 KB Time limit exceeded (wall clock)
7 Execution timed out 77 ms 25840 KB Time limit exceeded (wall clock)
8 Execution timed out 149 ms 40344 KB Time limit exceeded (wall clock)
9 Execution timed out 186 ms 30540 KB Time limit exceeded (wall clock)
10 Execution timed out 240 ms 44636 KB Time limit exceeded (wall clock)
11 Execution timed out 553 ms 40356 KB Time limit exceeded (wall clock)
12 Execution timed out 76 ms 21684 KB Time limit exceeded (wall clock)
13 Execution timed out 54 ms 21516 KB Time limit exceeded (wall clock)
14 Execution timed out 181 ms 25420 KB Time limit exceeded (wall clock)
15 Execution timed out 61 ms 24584 KB Time limit exceeded (wall clock)
16 Execution timed out 55 ms 28792 KB Time limit exceeded (wall clock)
17 Execution timed out 133 ms 32356 KB Time limit exceeded (wall clock)