oj.uz

답안 #934176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934176 2024-02-26T23:00:26 Z bobbilyking Regions (IOI09_regions) C++17
90 / 100
 6790 ms 78736 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 = 350;
// 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 11000 KB Output is correct
2 Correct 4 ms 11092 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 5 ms 10848 KB Output is correct
5 Correct 7 ms 10872 KB Output is correct
6 Correct 13 ms 10932 KB Output is correct
7 Correct 19 ms 10908 KB Output is correct
8 Correct 29 ms 10952 KB Output is correct
9 Correct 46 ms 11412 KB Output is correct
10 Correct 60 ms 11316 KB Output is correct
11 Correct 130 ms 11592 KB Output is correct
12 Correct 159 ms 11864 KB Output is correct
13 Correct 193 ms 11644 KB Output is correct
14 Correct 373 ms 12120 KB Output is correct
15 Correct 626 ms 15184 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1757 ms 21400 KB Output is correct
2 Correct 1571 ms 17908 KB Output is correct
3 Correct 4738 ms 21240 KB Output is correct
4 Correct 437 ms 12080 KB Output is correct
5 Correct 527 ms 14036 KB Output is correct
6 Correct 417 ms 27648 KB Output is correct
7 Correct 1240 ms 22644 KB Output is correct
8 Runtime error 122 ms 52040 KB Execution killed with signal 11
9 Correct 4958 ms 18936 KB Output is correct
10 Runtime error 3102 ms 78736 KB Execution killed with signal 6
11 Correct 6790 ms 18156 KB Output is correct
12 Correct 1776 ms 22604 KB Output is correct
13 Correct 2593 ms 22964 KB Output is correct
14 Correct 2384 ms 26664 KB Output is correct
15 Correct 5679 ms 27748 KB Output is correct
16 Correct 5878 ms 35116 KB Output is correct
17 Correct 5128 ms 37656 KB Output is correct