oj.uz

Submission #395443

# Submission time Handle Problem Language Result Execution time Memory
395443 2021-04-28T11:09:46 Z MarcoMeijer Regions (IOI09_regions) C++14
85 / 100
 8000 ms 32576 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 = 502;
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 ways[SQ][SQ];
int tot[MX];

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

    if(r < SQ) {
        memset(ways,0,sizeof(ways));

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

        // answer queries
        RE(_,q) {
            int r1, r2; IN(r1,r2);
            OUTL(ways[r1][r2]);
            cout.flush();
        }
    } else {
        RE1(u,n) dif[h[u]].pb(dfsPre[u]);
        RE1(i,r) sort(all(dif[i]));

        RE(_,q) {
            int r1, r2; IN(r1,r2);
            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 12 ms 16072 KB Output is correct
2 Correct 12 ms 16072 KB Output is correct
3 Correct 18 ms 16072 KB Output is correct
4 Correct 17 ms 16200 KB Output is correct
5 Correct 21 ms 16200 KB Output is correct
6 Correct 34 ms 16264 KB Output is correct
7 Correct 56 ms 16280 KB Output is correct
8 Correct 69 ms 16200 KB Output is correct
9 Correct 91 ms 16584 KB Output is correct
10 Correct 132 ms 16712 KB Output is correct
11 Correct 119 ms 16984 KB Output is correct
12 Correct 243 ms 17472 KB Output is correct
13 Correct 301 ms 17144 KB Output is correct
14 Correct 240 ms 17624 KB Output is correct
15 Correct 283 ms 19560 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 20496 KB Output is correct
2 Correct 1186 ms 19528 KB Output is correct
3 Correct 1973 ms 21992 KB Output is correct
4 Correct 420 ms 16200 KB Output is correct
5 Correct 487 ms 17420 KB Output is correct
6 Correct 1995 ms 17344 KB Output is correct
7 Correct 2193 ms 18596 KB Output is correct
8 Correct 1693 ms 22620 KB Output is correct
9 Correct 3157 ms 24336 KB Output is correct
10 Correct 5352 ms 28080 KB Output is correct
11 Correct 5798 ms 24456 KB Output is correct
12 Correct 6471 ms 25772 KB Output is correct
13 Correct 6874 ms 25736 KB Output is correct
14 Execution timed out 8057 ms 25748 KB Time limit exceeded
15 Execution timed out 8045 ms 29096 KB Time limit exceeded
16 Correct 7584 ms 32576 KB Output is correct
17 Execution timed out 8035 ms 31824 KB Time limit exceeded