oj.uz

답안 #934184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934184 2024-02-26T23:18:13 Z bobbilyking Regions (IOI09_regions) C++17
95 / 100
 4144 ms 52604 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 = 450;
// 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)
        assert(r1 != 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 3 ms 10840 KB Output is correct
2 Correct 2 ms 10848 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 12 ms 10840 KB Output is correct
7 Correct 17 ms 11096 KB Output is correct
8 Correct 20 ms 10840 KB Output is correct
9 Correct 29 ms 11280 KB Output is correct
10 Correct 44 ms 11364 KB Output is correct
11 Correct 82 ms 11608 KB Output is correct
12 Correct 107 ms 12120 KB Output is correct
13 Correct 132 ms 11748 KB Output is correct
14 Correct 220 ms 12176 KB Output is correct
15 Correct 233 ms 15380 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 978 ms 17616 KB Output is correct
2 Correct 1134 ms 15932 KB Output is correct
3 Correct 2012 ms 19464 KB Output is correct
4 Correct 174 ms 12568 KB Output is correct
5 Correct 241 ms 14344 KB Output is correct
6 Correct 426 ms 23816 KB Output is correct
7 Correct 1138 ms 16420 KB Output is correct
8 Runtime error 99 ms 52604 KB Execution killed with signal 11
9 Correct 2102 ms 19500 KB Output is correct
10 Correct 2582 ms 36108 KB Output is correct
11 Correct 4144 ms 19428 KB Output is correct
12 Correct 1102 ms 22608 KB Output is correct
13 Correct 1450 ms 23196 KB Output is correct
14 Correct 1708 ms 26780 KB Output is correct
15 Correct 2673 ms 28204 KB Output is correct
16 Correct 2540 ms 35888 KB Output is correct
17 Correct 2391 ms 37668 KB Output is correct