oj.uz

답안 #395433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395433 2021-04-28T10:53:38 Z MarcoMeijer Regions (IOI09_regions) C++14
30 / 100
 1459 ms 27160 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);
            FOR(u,withH[r2]) addFT(dfsPre[u], -1);
        }
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11464 KB Output is correct
2 Correct 8 ms 11464 KB Output is correct
3 Correct 10 ms 11500 KB Output is correct
4 Correct 13 ms 11464 KB Output is correct
5 Correct 19 ms 11464 KB Output is correct
6 Correct 25 ms 11464 KB Output is correct
7 Correct 48 ms 11592 KB Output is correct
8 Correct 29 ms 11620 KB Output is correct
9 Correct 89 ms 11892 KB Output is correct
10 Correct 102 ms 12004 KB Output is correct
11 Correct 171 ms 12232 KB Output is correct
12 Correct 241 ms 12700 KB Output is correct
13 Correct 275 ms 12432 KB Output is correct
14 Correct 191 ms 13020 KB Output is correct
15 Correct 249 ms 14920 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 837 ms 15808 KB Output is correct
2 Correct 1030 ms 14912 KB Output is correct
3 Correct 1459 ms 17344 KB Output is correct
4 Execution timed out 16 ms 11976 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 13260 KB Time limit exceeded (wall clock)
6 Execution timed out 23 ms 13144 KB Time limit exceeded (wall clock)
7 Execution timed out 30 ms 14080 KB Time limit exceeded (wall clock)
8 Execution timed out 38 ms 17984 KB Time limit exceeded (wall clock)
9 Execution timed out 68 ms 19008 KB Time limit exceeded (wall clock)
10 Execution timed out 61 ms 22652 KB Time limit exceeded (wall clock)
11 Execution timed out 76 ms 19012 KB Time limit exceeded (wall clock)
12 Execution timed out 85 ms 20620 KB Time limit exceeded (wall clock)
13 Execution timed out 74 ms 20508 KB Time limit exceeded (wall clock)
14 Execution timed out 93 ms 20416 KB Time limit exceeded (wall clock)
15 Execution timed out 68 ms 23684 KB Time limit exceeded (wall clock)
16 Execution timed out 73 ms 27160 KB Time limit exceeded (wall clock)
17 Execution timed out 80 ms 26360 KB Time limit exceeded (wall clock)