oj.uz

Submission #395414

# Submission time Handle Problem Language Result Execution time Memory
395414 2021-04-28T10:36:54 Z MarcoMeijer Regions (IOI09_regions) C++14
30 / 100
 1624 ms 11216 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);

int n, r, q;
int h[MX], p[MX];
vi withH[SQ];
vi chl[MX];
int ways[SQ][SQ];
int tot[MX];

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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 8 ms 6784 KB Output is correct
4 Correct 11 ms 6728 KB Output is correct
5 Correct 14 ms 6728 KB Output is correct
6 Correct 36 ms 6836 KB Output is correct
7 Correct 49 ms 6856 KB Output is correct
8 Correct 58 ms 6896 KB Output is correct
9 Correct 45 ms 6984 KB Output is correct
10 Correct 133 ms 7212 KB Output is correct
11 Correct 169 ms 7368 KB Output is correct
12 Correct 141 ms 7700 KB Output is correct
13 Correct 309 ms 7528 KB Output is correct
14 Correct 162 ms 8032 KB Output is correct
15 Correct 297 ms 8504 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 9992 KB Output is correct
2 Correct 1202 ms 9404 KB Output is correct
3 Correct 1624 ms 10684 KB Output is correct
4 Runtime error 9 ms 10104 KB Execution killed with signal 11
5 Runtime error 9 ms 10272 KB Execution killed with signal 11
6 Runtime error 9 ms 10304 KB Execution killed with signal 11
7 Runtime error 10 ms 10544 KB Execution killed with signal 11
8 Runtime error 9 ms 10440 KB Execution killed with signal 11
9 Runtime error 10 ms 10672 KB Execution killed with signal 11
10 Runtime error 10 ms 10696 KB Execution killed with signal 11
11 Runtime error 11 ms 11216 KB Execution killed with signal 11
12 Runtime error 10 ms 10824 KB Execution killed with signal 11
13 Runtime error 9 ms 10752 KB Execution killed with signal 11
14 Runtime error 10 ms 11052 KB Execution killed with signal 11
15 Runtime error 9 ms 10312 KB Execution killed with signal 11
16 Runtime error 11 ms 10824 KB Execution killed with signal 11
17 Runtime error 10 ms 10952 KB Execution killed with signal 11