답안 #934167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934167 2024-02-26T22:48:42 Z bobbilyking Regions (IOI09_regions) C++17
90 / 100
5820 ms 48080 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 RR = 2.5e4 + 1;
const ll AMT = RR / HEAVYTH + 2;

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];
    }
}


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

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

    // 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] << endl;
        } else if (people[r2].size() >= HEAVYTH) {
            cout << containsHeavy[lower_bound(A(heavies), r2) - heavies.begin()][r1] << endl;
        } 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 << ans << endl;
            for (auto x: people[r2]) seg::modify(tin[x], 0);
        }
    }
}

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:146:5: note: in expansion of macro 'F'
  146 |     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:150:5: note: in expansion of macro 'F'
  150 |     F(i, 0, heavies.size()) {
      |     ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 6 ms 10584 KB Output is correct
6 Correct 12 ms 10584 KB Output is correct
7 Correct 17 ms 10584 KB Output is correct
8 Correct 20 ms 10860 KB Output is correct
9 Correct 37 ms 11312 KB Output is correct
10 Correct 60 ms 11220 KB Output is correct
11 Correct 109 ms 11512 KB Output is correct
12 Correct 140 ms 11864 KB Output is correct
13 Correct 157 ms 11876 KB Output is correct
14 Correct 292 ms 12120 KB Output is correct
15 Correct 536 ms 15260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1492 ms 21312 KB Output is correct
2 Correct 1295 ms 17812 KB Output is correct
3 Correct 3882 ms 21380 KB Output is correct
4 Correct 303 ms 12260 KB Output is correct
5 Correct 398 ms 14196 KB Output is correct
6 Incorrect 355 ms 23600 KB Output isn't correct
7 Correct 2019 ms 20416 KB Output is correct
8 Runtime error 81 ms 48080 KB Execution killed with signal 11
9 Correct 4375 ms 19140 KB Output is correct
10 Correct 5514 ms 35800 KB Output is correct
11 Correct 5820 ms 18156 KB Output is correct
12 Correct 1587 ms 22704 KB Output is correct
13 Correct 2478 ms 23376 KB Output is correct
14 Correct 2229 ms 26848 KB Output is correct
15 Correct 5363 ms 27928 KB Output is correct
16 Correct 5548 ms 35148 KB Output is correct
17 Correct 4668 ms 37736 KB Output is correct