oj.uz

Submission #395501

# Submission time Handle Problem Language Result Execution time Memory
395501 2021-04-28T12:12:38 Z MarcoMeijer Regions (IOI09_regions) C++14
83 / 100
 8000 ms 46944 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
    RE1(i,m) 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] <= 300) {
                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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15944 KB Output is correct
2 Runtime error 28 ms 32220 KB Execution killed with signal 11
3 Runtime error 28 ms 32236 KB Execution killed with signal 11
4 Correct 14 ms 15944 KB Output is correct
5 Correct 21 ms 16072 KB Output is correct
6 Correct 40 ms 16164 KB Output is correct
7 Correct 43 ms 16160 KB Output is correct
8 Correct 52 ms 16200 KB Output is correct
9 Correct 102 ms 16832 KB Output is correct
10 Correct 206 ms 16816 KB Output is correct
11 Correct 220 ms 17264 KB Output is correct
12 Correct 351 ms 18136 KB Output is correct
13 Correct 401 ms 17828 KB Output is correct
14 Correct 379 ms 18760 KB Output is correct
15 Correct 514 ms 22940 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 23412 KB Output is correct
2 Correct 1890 ms 22088 KB Output is correct
3 Correct 1837 ms 26236 KB Output is correct
4 Correct 754 ms 18572 KB Output is correct
5 Correct 809 ms 20932 KB Output is correct
6 Correct 1423 ms 20352 KB Output is correct
7 Correct 2163 ms 21720 KB Output is correct
8 Correct 2398 ms 29564 KB Output is correct
9 Correct 6426 ms 30068 KB Output is correct
10 Correct 4451 ms 37376 KB Output is correct
11 Execution timed out 8032 ms 30744 KB Time limit exceeded
12 Execution timed out 8015 ms 31268 KB Time limit exceeded
13 Correct 7435 ms 32076 KB Output is correct
14 Execution timed out 8016 ms 32108 KB Time limit exceeded
15 Correct 5887 ms 37992 KB Output is correct
16 Correct 5407 ms 46944 KB Output is correct
17 Correct 5178 ms 45484 KB Output is correct