oj.uz

답안 #395452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395452 2021-04-28T11:18:46 Z MarcoMeijer Regions (IOI09_regions) C++14
95 / 100
 8000 ms 35940 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 m;
int ways[SQ][SQ];
int tot[MX];
int sh[MX], rh[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);

    // 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];
    }

    // 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 {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16200 KB Output is correct
2 Correct 11 ms 16200 KB Output is correct
3 Correct 18 ms 16200 KB Output is correct
4 Correct 15 ms 16200 KB Output is correct
5 Correct 22 ms 16200 KB Output is correct
6 Correct 28 ms 16200 KB Output is correct
7 Correct 55 ms 16200 KB Output is correct
8 Correct 61 ms 16328 KB Output is correct
9 Correct 86 ms 16584 KB Output is correct
10 Correct 133 ms 16840 KB Output is correct
11 Correct 120 ms 17108 KB Output is correct
12 Correct 182 ms 17676 KB Output is correct
13 Correct 265 ms 17516 KB Output is correct
14 Correct 274 ms 18160 KB Output is correct
15 Correct 237 ms 20184 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 21480 KB Output is correct
2 Correct 953 ms 20536 KB Output is correct
3 Correct 1785 ms 23144 KB Output is correct
4 Correct 428 ms 18216 KB Output is correct
5 Correct 561 ms 19528 KB Output is correct
6 Correct 782 ms 19632 KB Output is correct
7 Correct 995 ms 21040 KB Output is correct
8 Correct 1598 ms 25280 KB Output is correct
9 Correct 2776 ms 27104 KB Output is correct
10 Correct 3057 ms 31180 KB Output is correct
11 Correct 4738 ms 27780 KB Output is correct
12 Correct 5660 ms 29028 KB Output is correct
13 Correct 6435 ms 28976 KB Output is correct
14 Correct 7771 ms 29116 KB Output is correct
15 Execution timed out 8051 ms 32540 KB Time limit exceeded
16 Correct 6400 ms 35940 KB Output is correct
17 Correct 6569 ms 35112 KB Output is correct