Submission #727510

#	Time	Username	Problem	Language	Result	Execution time	Memory
727510		CutSandstone	Regions (IOI09_regions)	C++17	95 / 100	5818 ms	131072 KiB

regions

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define f first
#define s second
#define pb push_back
#define inf ~((long long)1<<63)
using namespace std;
const int mod = 1000000007;
void setio(string name = "") { 
    ios::sync_with_stdio(false), cin.tie(nullptr); 
    if(name.length()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
class BIT {
  private:
    int size;
    vector<int> bit;
  public:
    BIT(int size) : size(size), bit(size + 1) {}
    void add(int ind, int val){for(ind++; ind <= size; ind += ind & -ind) { bit[ind] += val; };}
    int prev(int ind) {
        int total = 0;
        for (ind++; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
        return total;
    }
    int sum(int a, int b){
        return prev(b)-(a == 0 ? 0:prev(a-1));
    }
};
int N, R, timer = 0;
vector<vector<int>> cnt;
vector<int> big;
vector<int> st, en;
vector<vector<int>> g;
vector<vector<int>> ans;
vector<int> nums;
vector<BIT> sums;
void dfs(int s, vector<int>& curr){
    if(big[nums[s]]+1) curr[big[nums[s]]]++;
    else for(int i = 0; i<curr.size(); i++) ans[s][i] = curr[i];
    st[s] = timer++;
    for(int i: g[s]) dfs(i, curr);
    if(big[nums[s]]+1) curr[big[nums[s]]]--;
    en[s] = timer-1;
}
int main() {
    setio();
    int Q; cin >> N >> R >> Q;
    g.resize(N, vector<int>(0));
    nums.resize(N);
    cin >> nums[0];
    for(int i = 1; i<N; i++){
        int par; cin >> par;
        g[par-1].pb(i);
        cin >> nums[i];
    }
    cnt.resize(R, vector<int>(0));
    for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
    int sqrt = 1;
    while(sqrt*sqrt <= N) sqrt++;
    big.resize(R, -1);
    int p = 0;
    for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
    st.resize(N);
    en.resize(N);
    ans.resize(N, vector<int>(p));
    vector<int> curr(p);
    dfs(0, curr);
    sums.resize(p, BIT(N));
    for(int i = 0; i<N; i++) if(big[nums[i]]+1) sums[big[nums[i]]].add(st[i], 1);
    BIT b(N);
    map<int, int> mem;
    while(Q--> 0){
        int up, down; cin >> up >> down; --up, --down;
        if(mem.find(up*R+down) != mem.end()) cout << mem[up*R+down] << endl;
        else if(big[down]+1){
            int ret = 0;
            for(int i: cnt[up]) ret+=sums[big[down]].sum(st[i], en[i]);
            mem[up*R+down] = ret;
            cout << ret << endl;
        }else if(big[up]+1){
            int ret = 0;
            for(int i: cnt[down])
                ret+=ans[i][big[up]];
            mem[up*R+down] = ret;
            cout << ret << endl;
        }else{
            int ret = 0;
            for(int i: cnt[down]) b.add(st[i], 1);
            for(int i: cnt[up]) ret+=b.sum(st[i], en[i])-(up == down ? 1:0);
            for(int i: cnt[down]) b.add(st[i], -1);
            mem[up*R+down] = ret;
            cout << ret << endl;
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, std::vector<int>&)':
regions.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     else for(int i = 0; i<curr.size(); i++) ans[s][i] = curr[i];
      |                         ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:68:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
      |                                 ~~~~~~~~~~~~~~^~~~~~~
regions.cpp: In function 'void setio(std::string)':
regions.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 80 / 85