oj.uz

Submission #395507

# Submission time Handle Problem Language Result Execution time Memory
395507 2021-04-28T12:16:33 Z MarcoMeijer Regions (IOI09_regions) C++14
100 / 100
 7426 ms 45960 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 2e5+10;
const int SQ = 450;
const int N = (1<<20);

// input
int n, r, q;
int h[MX];
vi withH[MX];

// tree
vi chl[MX];
int dfsPre[MX], treeBg[MX], treeEd[MX], curDFS=0;
void dfs(int u) {
    treeBg[u] = curDFS;
    dfsPre[u] = curDFS++;
    FOR(v,chl[u]) dfs(v);
    treeEd[u] = curDFS-1;
}

// R > 500
vi dif[MX];

// R <= 500
int m;
int ways[SQ][SQ];
int tot[MX];
int sh[MX], rh[MX];

vii regions[SQ];
void dfs2(int u, int cr, int sm) {
    if(regions[cr].empty()) regions[cr].pb({0,0});
    if(rh[h[u]] == cr)
        sm++, regions[cr].pb({treeBg[u], sm});
    FOR(v,chl[u]) dfs2(v,cr,sm);
    if(rh[h[u]] == cr)
        sm--, regions[cr].pb({treeEd[u]+1, sm});
}

void program() {
    // input
    IN(n,r,q);
    RE1(i,n) {
        if(i != 1) {
            int p; IN(p);
            chl[p].pb(i);
        }
        IN(h[i]);
    }
    dfs(1);
    RE1(i,n) withH[h[i]].pb(i);

    // R >= 500
    RE1(u,n) dif[h[u]].pb(dfsPre[u]);
    RE1(i,r) sort(all(dif[i]));

    // R <= 500
    RE1(i,n) sh[i] = i;
    sort(sh+1,sh+n+1, [](int i, int j) {
        return withH[i].size() > withH[j].size();
    });
    RE1(i,n) rh[sh[i]] = i;
    m = min(r,SQ-2);

    // fill tot
    memset(ways,0,sizeof(ways));
    RE1(j,m) {
        memset(tot,0,sizeof(tot));
        FOR(u,withH[sh[j]]) tot[u] = 1;
        REV(u,1,n+1) FOR(v,chl[u]) tot[u] += tot[v];
        RE1(i,m) FOR(u,withH[sh[i]]) ways[i][j] += tot[u];
    }

    // dfs 2
    int o = min(m,200);
    RE1(i,o) dfs2(1,i,0);

    // answer queries
    RE(_,q) {
        int r1, r2; IN(r1,r2);
        if(rh[r1] <= m && rh[r2] <= m) {
            OUTL(ways[rh[r1]][rh[r2]]);
            cout.flush();
        } else {
            if(rh[r1] <= o) {
                int res = 0;
                FOR(u,withH[r2]) res += (--upper_bound(all(regions[rh[r1]]),ii{dfsPre[u],1e9}))->se;
                OUTL(res);
                cout.flush();
            } else {
                int res = 0;
                FOR(u,withH[r1]) res += upper_bound(all(dif[r2]),treeEd[u]) - lower_bound(all(dif[r2]),treeBg[u]);
                OUTL(res);
                cout.flush();
            }
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15944 KB Output is correct
2 Correct 13 ms 16020 KB Output is correct
3 Correct 23 ms 16016 KB Output is correct
4 Correct 20 ms 15928 KB Output is correct
5 Correct 19 ms 16020 KB Output is correct
6 Correct 31 ms 16104 KB Output is correct
7 Correct 40 ms 16128 KB Output is correct
8 Correct 80 ms 16200 KB Output is correct
9 Correct 65 ms 16804 KB Output is correct
10 Correct 183 ms 16664 KB Output is correct
11 Correct 209 ms 17264 KB Output is correct
12 Correct 281 ms 17860 KB Output is correct
13 Correct 334 ms 17720 KB Output is correct
14 Correct 346 ms 18792 KB Output is correct
15 Correct 457 ms 22688 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 23412 KB Output is correct
2 Correct 1451 ms 22148 KB Output is correct
3 Correct 1488 ms 26000 KB Output is correct
4 Correct 558 ms 18496 KB Output is correct
5 Correct 461 ms 20696 KB Output is correct
6 Correct 1039 ms 20208 KB Output is correct
7 Correct 1543 ms 21600 KB Output is correct
8 Correct 1622 ms 29280 KB Output is correct
9 Correct 4698 ms 29028 KB Output is correct
10 Correct 3598 ms 36468 KB Output is correct
11 Correct 7426 ms 29564 KB Output is correct
12 Correct 6071 ms 30376 KB Output is correct
13 Correct 4623 ms 31016 KB Output is correct
14 Correct 6169 ms 30996 KB Output is correct
15 Correct 4530 ms 36860 KB Output is correct
16 Correct 4273 ms 45960 KB Output is correct
17 Correct 3991 ms 44432 KB Output is correct