oj.uz

답안 #395497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395497 2021-04-28T12:08:06 Z MarcoMeijer Regions (IOI09_regions) C++14
80 / 100
 8000 ms 47348 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];

vii regions[SQ];
void dfs2(int u, int cr, int sm) {
    if(regions[cr].empty()) regions[cr].pb({0,0});
    if(rh[h[u]] == cr)
        sm++, regions[cr].pb({treeBg[u], sm});
    FOR(v,chl[u]) dfs2(v,cr,sm);
    if(rh[h[u]] == cr)
        sm--, regions[cr].pb({treeEd[u]+1, sm});
}

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

    // dfs 2
    RE1(i,m) dfs2(1,i,0);

    // 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 {
            if(rh[r1] <= m) {
                int res = 0;
                FOR(u,withH[r2]) res += (--upper_bound(all(regions[rh[r1]]),ii{dfsPre[u],1e9}))->se;
                OUTL(res);
                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 17 ms 16200 KB Output is correct
4 Correct 16 ms 16184 KB Output is correct
5 Correct 17 ms 16248 KB Output is correct
6 Correct 35 ms 16300 KB Output is correct
7 Correct 31 ms 16328 KB Output is correct
8 Correct 53 ms 16356 KB Output is correct
9 Correct 102 ms 16964 KB Output is correct
10 Correct 227 ms 17024 KB Output is correct
11 Correct 297 ms 17464 KB Output is correct
12 Correct 293 ms 18332 KB Output is correct
13 Correct 408 ms 18016 KB Output is correct
14 Correct 377 ms 18980 KB Output is correct
15 Correct 474 ms 23024 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1474 ms 23604 KB Output is correct
2 Correct 1877 ms 22276 KB Output is correct
3 Correct 1569 ms 26428 KB Output is correct
4 Correct 692 ms 18744 KB Output is correct
5 Correct 723 ms 21184 KB Output is correct
6 Correct 1723 ms 20444 KB Output is correct
7 Correct 2181 ms 21980 KB Output is correct
8 Correct 2435 ms 29824 KB Output is correct
9 Execution timed out 8026 ms 30400 KB Time limit exceeded
10 Correct 4842 ms 37776 KB Output is correct
11 Execution timed out 8012 ms 31152 KB Time limit exceeded
12 Execution timed out 8016 ms 30924 KB Time limit exceeded
13 Correct 7696 ms 32416 KB Output is correct
14 Execution timed out 8058 ms 32288 KB Time limit exceeded
15 Correct 5702 ms 38252 KB Output is correct
16 Correct 5378 ms 47348 KB Output is correct
17 Correct 4973 ms 45836 KB Output is correct