oj.uz

Submission #395434

# Submission time Handle Problem Language Result Execution time Memory
395434 2021-04-28T10:57:19 Z MarcoMeijer Regions (IOI09_regions) C++14
70 / 100
 8000 ms 27248 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;
}

// fenwick tree
int FT[MX];
void addFT(int i, int value) {
    for(i++; i<=n+1; i+=i&-i) FT[i] += value;
}
int getFT(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans += FT[i];
    return ans;
}

// 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 {
        memset(FT,0,sizeof(FT));

        RE(_,q) {
            int r1, r2; IN(r1,r2);
            FOR(u,withH[r2]) addFT(dfsPre[u],  1);
            int res = 0;
            FOR(u,withH[r1]) res += getFT(treeEd[u]) - getFT(treeBg[u]);
            OUTL(res);
            cout.flush();
            FOR(u,withH[r2]) addFT(dfsPre[u], -1);
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11464 KB Output is correct
2 Correct 7 ms 11392 KB Output is correct
3 Correct 10 ms 11464 KB Output is correct
4 Correct 13 ms 11464 KB Output is correct
5 Correct 13 ms 11464 KB Output is correct
6 Correct 38 ms 11572 KB Output is correct
7 Correct 49 ms 11464 KB Output is correct
8 Correct 37 ms 11620 KB Output is correct
9 Correct 76 ms 11848 KB Output is correct
10 Correct 150 ms 11976 KB Output is correct
11 Correct 154 ms 12232 KB Output is correct
12 Correct 178 ms 12616 KB Output is correct
13 Correct 193 ms 12360 KB Output is correct
14 Correct 240 ms 13016 KB Output is correct
15 Correct 295 ms 14896 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 15816 KB Output is correct
2 Correct 1163 ms 14836 KB Output is correct
3 Correct 1623 ms 17300 KB Output is correct
4 Correct 404 ms 12004 KB Output is correct
5 Correct 478 ms 13256 KB Output is correct
6 Correct 1793 ms 13200 KB Output is correct
7 Correct 2599 ms 14020 KB Output is correct
8 Correct 2712 ms 18004 KB Output is correct
9 Correct 4273 ms 18992 KB Output is correct
10 Correct 7211 ms 22720 KB Output is correct
11 Correct 7437 ms 19008 KB Output is correct
12 Execution timed out 8071 ms 20668 KB Time limit exceeded
13 Execution timed out 8068 ms 20508 KB Time limit exceeded
14 Execution timed out 8055 ms 20448 KB Time limit exceeded
15 Execution timed out 8074 ms 23724 KB Time limit exceeded
16 Execution timed out 8007 ms 27248 KB Time limit exceeded
17 Execution timed out 8058 ms 26432 KB Time limit exceeded