oj.uz

답안 #934175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934175 2024-02-26T23:00:09 Z bobbilyking Regions (IOI09_regions) C++17
95 / 100
 8000 ms 38552 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];
    }
}


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

    vl selfs(RR);

    F(i, 1, RR) if (people[i].size()) {
        for (auto x: people[i]) seg::modify(tin[x], 1);
        for (auto x: people[i]) selfs[i] += seg::query(tin[x], tout[x]);
        for (auto x: people[i]) seg::modify(tin[x], 0);
        selfs[i] -= people[i].size();
    }
    
    while (q--) {
        G(r1) G(r2)
        if (r1 == r2) {
            cout << selfs[r1] << endl;
            continue;
        }
        
        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 {
            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:147:5: note: in expansion of macro 'F'
  147 |     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:151:5: note: in expansion of macro 'F'
  151 |     F(i, 0, heavies.size()) {
      |     ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 4 ms 10848 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 12 ms 10948 KB Output is correct
7 Correct 18 ms 10840 KB Output is correct
8 Correct 24 ms 10956 KB Output is correct
9 Correct 41 ms 11428 KB Output is correct
10 Correct 59 ms 11360 KB Output is correct
11 Correct 127 ms 11652 KB Output is correct
12 Correct 160 ms 12120 KB Output is correct
13 Correct 189 ms 11724 KB Output is correct
14 Correct 330 ms 12120 KB Output is correct
15 Correct 608 ms 15412 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1783 ms 19804 KB Output is correct
2 Correct 1607 ms 18340 KB Output is correct
3 Correct 4238 ms 21832 KB Output is correct
4 Correct 389 ms 12168 KB Output is correct
5 Correct 472 ms 14212 KB Output is correct
6 Correct 2166 ms 13440 KB Output is correct
7 Correct 3076 ms 14372 KB Output is correct
8 Correct 4152 ms 20428 KB Output is correct
9 Correct 5217 ms 19888 KB Output is correct
10 Execution timed out 8045 ms 25748 KB Time limit exceeded
11 Correct 7076 ms 19344 KB Output is correct
12 Correct 1801 ms 23684 KB Output is correct
13 Correct 2689 ms 23988 KB Output is correct
14 Correct 2500 ms 27732 KB Output is correct
15 Correct 5743 ms 28812 KB Output is correct
16 Correct 5860 ms 36188 KB Output is correct
17 Correct 5475 ms 38552 KB Output is correct