답안 #403247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403247 2021-05-13T00:18:51 Z rqi Regions (IOI09_regions) C++14
100 / 100
2890 ms 38332 KB
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const int MOD = 1e9+7;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mx = 200005;
const int BLOCK = 447;
const int REGION_mx = 25005;
//const int REGION_mx = 25;
int N, R, Q;

int par[mx];
vi children[mx];
int etind[mx]; //etind of an employee
pi etquery[mx];

int H[mx];
vi region_empls[REGION_mx]; // employees of a region
int sorted_region_ind[REGION_mx];
vpi region_queries[REGION_mx]; //count prefix up to f s times
vi region_updates[REGION_mx]; //update position +1

int pans[mx/BLOCK+5][REGION_mx];
int cans[mx/BLOCK+5][REGION_mx];

int cur_etind = 0;

void dfs(int node){
    etind[node] = ++cur_etind;
    etquery[node].f = cur_etind;
    for(auto u: children[node]){
        dfs(u);
    }
    etquery[node].s = cur_etind;
}

void genETinds(){
    dfs(1);
    assert(cur_etind == N);
}

int csum[mx];

void precomputeAnses(){
    for(int r = 1; r <= R; r++){
        if(sz(region_empls[r]) > BLOCK){
            //do pans, cans[sorted_region_ind]
            for(int i = N; i >= 0; i--){
                csum[i] = 0;
            }
            for(auto &u: region_queries[r]){
                csum[u.f]+=u.s;
            }
            for(int i = N; i >= 0; i--){
                csum[i]+=csum[i+1];
            }
            for(int i = 1; i <= R; i++){
                for(auto &u: region_updates[i]){
                    pans[sorted_region_ind[r]][i]+=csum[u];
                    #warning overflow
                }
            }

            for(int i = 0; i <= N; i++){
                csum[i] = 0;
            }
            for(auto &u: region_updates[r]){
                csum[u]++;
            }
            for(int i = 1; i <= N; i++){
                csum[i]+=csum[i-1];
            }
            for(int i = 1; i <= R; i++){
                for(auto &u: region_queries[i]){
                    cans[sorted_region_ind[r]][i]+=csum[u.f]*u.s;
                    #warning overflow
                }
            }
        }
    }
}

int solveSmall(int r1, int r2){
    // cout << "solving Small" << "\n";
    // for(auto u: region_queries[r1]){
    //     cout << "region_queries: " << u.f << " " << u.s << "\n";
    // }
    // for(auto u: region_updates[r2]){
    //     cout << "region_updates: " <<  u << "\n";
    // }
    int query_ind = 0;
    int update_ind = 0;
    int res = 0;
    int cur = 0;
    while(true){
        int query_num = MOD;
        int update_num = MOD;
        if(query_ind < sz(region_queries[r1])){
            query_num = region_queries[r1][query_ind].f;
        }
        if(update_ind < sz(region_updates[r2])){
            update_num = region_updates[r2][update_ind];
        }
        if(query_num == MOD && update_num == MOD) break;

        //cout << "query, update ind: " << query_ind << " " << update_ind << "\n";
        if(update_num <= query_num){
            
            cur++;
            //cout << "updated" << "\n";
            update_ind++;
        }
        else{
            
            res+=cur*region_queries[r1][query_ind].s;
            //cout << "queried " << res << "\n";
            query_ind++;
        }
    }

    return res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> R >> Q;
    for(int i = 1; i <= N; i++){
        if(i != 1){
            cin >> par[i];
            children[par[i]].pb(i);
        }
        cin >> H[i];
        region_empls[H[i]].pb(i);
    }

    genETinds();
    // for(int i = 1; i <= N; i++){
    //     cout << "etind: " << i << " " << etind[i] << "\n";
    // }
    vpi sort_by_region_size;
    for(int i = 1; i <= R; i++){
        sort_by_region_size.pb(mp(sz(region_empls[i]), i));
    }
    sort(sort_by_region_size.rbegin(), sort_by_region_size.rend());
    for(int i = 0; i < R; i++){
        sorted_region_ind[sort_by_region_size[i].s] = i;
    }

    for(int i = 1; i <= N; i++){
        region_queries[H[i]].pb(mp(etquery[i].f-1, -1));
        region_queries[H[i]].pb(mp(etquery[i].s, 1));
        region_updates[H[i]].pb(etind[i]);
    }

    for(int i = 1; i <= R; i++){
        sort(all(region_queries[i]));
        sort(all(region_updates[i]));
    }

    precomputeAnses();

    for(int i = 1; i <= Q; i++){
        int r1, r2;
        cin >> r1 >> r2;
        int ans = -1;
        if(sz(region_empls[r1]) > BLOCK){
            ans = pans[sorted_region_ind[r1]][r2];
        }
        else if(sz(region_empls[r2]) > BLOCK){
            ans = cans[sorted_region_ind[r2]][r1];
        }
        else{
            ans = solveSmall(r1, r2);
        }
        cout << ans << "\n";
        cout.flush();
    }
    #warning int overflow
}

Compilation message

regions.cpp:78:22: warning: #warning overflow [-Wcpp]
   78 |                     #warning overflow
      |                      ^~~~~~~
regions.cpp:94:22: warning: #warning overflow [-Wcpp]
   94 |                     #warning overflow
      |                      ^~~~~~~
regions.cpp:196:6: warning: #warning int overflow [-Wcpp]
  196 |     #warning int overflow
      |      ^~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6796 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 7 ms 6728 KB Output is correct
4 Correct 7 ms 6728 KB Output is correct
5 Correct 14 ms 6856 KB Output is correct
6 Correct 30 ms 6856 KB Output is correct
7 Correct 44 ms 6856 KB Output is correct
8 Correct 36 ms 6984 KB Output is correct
9 Correct 55 ms 7432 KB Output is correct
10 Correct 107 ms 7624 KB Output is correct
11 Correct 114 ms 8140 KB Output is correct
12 Correct 136 ms 8836 KB Output is correct
13 Correct 187 ms 8648 KB Output is correct
14 Correct 222 ms 9664 KB Output is correct
15 Correct 218 ms 12412 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 14048 KB Output is correct
2 Correct 1062 ms 13096 KB Output is correct
3 Correct 1704 ms 16272 KB Output is correct
4 Correct 285 ms 9664 KB Output is correct
5 Correct 407 ms 11208 KB Output is correct
6 Correct 707 ms 15296 KB Output is correct
7 Correct 945 ms 14784 KB Output is correct
8 Correct 1002 ms 27748 KB Output is correct
9 Correct 1594 ms 21776 KB Output is correct
10 Correct 2468 ms 38332 KB Output is correct
11 Correct 2890 ms 22720 KB Output is correct
12 Correct 1046 ms 24248 KB Output is correct
13 Correct 1423 ms 24396 KB Output is correct
14 Correct 1592 ms 28004 KB Output is correct
15 Correct 2311 ms 29236 KB Output is correct
16 Correct 2421 ms 33980 KB Output is correct
17 Correct 2260 ms 36696 KB Output is correct