oj.uz

답안 #934187

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934187 2024-02-26T23:23:28 Z bobbilyking Regions (IOI09_regions) C++17
100 / 100
 3478 ms 38024 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 HEAVYTH = 550;
// const ll HEAVYTH = 750;
const ll RR = 2.5e4 + 1;
const ll AMT = RR / HEAVYTH + 6;

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

vl dfsorder;
vl heavies;


ll sz[NN];


void dfsinit(ll i) {
    static int time = 0;
    tin[i] = time++;
    dfsorder.push_back(i);
    sort(A(adj[i]), [&](ll a, ll b) {
        return sz[a] > sz[b];
    });
    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];
    }
}

vl peopleWhenQuerying[RR];

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);

    vl p(n+1);
    F(i, 2, n+1) {
        G(par) cin >> label[i]; 
        adj[par].push_back(i);
        people[label[i]].push_back(i);

        p[i] = par;
    }

    FD(i, n, 1) sz[p[i]]+= ++sz[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);
    }

    F(i, 1, r+1) if (people[i].size() < HEAVYTH) {
        peopleWhenQuerying[i] = people[i];
        for (auto &x: peopleWhenQuerying[i]) x = tin[x];
        sort(A(peopleWhenQuerying[i]));
    }

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

    // exit(0);
    
    while (q--) {
        G(r1) G(r2)
        
        if (people[r1].size() >= HEAVYTH) {
            cout << heavyRoot[lower_bound(A(heavies), r1) - heavies.begin()][r2] << endl;
        } else if (people[r2].size() >= HEAVYTH) {
            cout << containsHeavy[lower_bound(A(heavies), r2) - heavies.begin()][r1] << endl;
        } else {
            ll ans = 0;
            for (auto x: people[r1]) {
                ans += lower_bound(A(peopleWhenQuerying[r2]), tout[x]) - lower_bound(A(peopleWhenQuerying[r2]), tin[x]);
            }
            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:22:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                                     ^
regions.cpp:126:5: note: in expansion of macro 'F'
  126 |     F(i, 0, heavies.size()) {
      |     ^
regions.cpp:22:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                                     ^
regions.cpp:130:5: note: in expansion of macro 'F'
  130 |     F(i, 0, heavies.size()) {
      |     ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 5 ms 10840 KB Output is correct
6 Correct 11 ms 10840 KB Output is correct
7 Correct 16 ms 10840 KB Output is correct
8 Correct 23 ms 10840 KB Output is correct
9 Correct 29 ms 11352 KB Output is correct
10 Correct 40 ms 11384 KB Output is correct
11 Correct 70 ms 11608 KB Output is correct
12 Correct 91 ms 12120 KB Output is correct
13 Correct 107 ms 11744 KB Output is correct
14 Correct 198 ms 12120 KB Output is correct
15 Correct 193 ms 15316 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 955 ms 19684 KB Output is correct
2 Correct 968 ms 18068 KB Output is correct
3 Correct 1747 ms 21648 KB Output is correct
4 Correct 209 ms 12376 KB Output is correct
5 Correct 214 ms 14340 KB Output is correct
6 Correct 1097 ms 13632 KB Output is correct
7 Correct 1253 ms 14552 KB Output is correct
8 Correct 923 ms 20340 KB Output is correct
9 Correct 1663 ms 19784 KB Output is correct
10 Correct 3478 ms 25952 KB Output is correct
11 Correct 3420 ms 19616 KB Output is correct
12 Correct 854 ms 22872 KB Output is correct
13 Correct 1237 ms 23200 KB Output is correct
14 Correct 1416 ms 26880 KB Output is correct
15 Correct 2211 ms 28216 KB Output is correct
16 Correct 2175 ms 36056 KB Output is correct
17 Correct 1937 ms 38024 KB Output is correct