oj.uz

답안 #934174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934174 2024-02-26T22:59:47 Z bobbilyking Regions (IOI09_regions) C++17
95 / 100
 6728 ms 48904 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];
    }
}


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 2 ms 10584 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 5 ms 10852 KB Output is correct
5 Correct 5 ms 10880 KB Output is correct
6 Correct 13 ms 10940 KB Output is correct
7 Correct 16 ms 10928 KB Output is correct
8 Correct 19 ms 10948 KB Output is correct
9 Correct 34 ms 11440 KB Output is correct
10 Correct 64 ms 11368 KB Output is correct
11 Correct 112 ms 11656 KB Output is correct
12 Correct 139 ms 12120 KB Output is correct
13 Correct 148 ms 11988 KB Output is correct
14 Correct 302 ms 12156 KB Output is correct
15 Correct 547 ms 15184 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1564 ms 21624 KB Output is correct
2 Correct 1310 ms 20252 KB Output is correct
3 Correct 3973 ms 23872 KB Output is correct
4 Correct 309 ms 12376 KB Output is correct
5 Correct 390 ms 14292 KB Output is correct
6 Correct 376 ms 23868 KB Output is correct
7 Correct 2084 ms 20708 KB Output is correct
8 Runtime error 84 ms 48904 KB Execution killed with signal 11
9 Correct 4666 ms 19920 KB Output is correct
10 Correct 6284 ms 36468 KB Output is correct
11 Correct 6639 ms 19132 KB Output is correct
12 Correct 2229 ms 23372 KB Output is correct
13 Correct 2971 ms 24252 KB Output is correct
14 Correct 2699 ms 27636 KB Output is correct
15 Correct 6728 ms 28892 KB Output is correct
16 Correct 6585 ms 35920 KB Output is correct
17 Correct 5638 ms 38464 KB Output is correct