oj.uz

Submission #727503

# Submission time Handle Problem Language Result Execution time Memory
727503 2023-04-20T21:37:19 Z CutSandstone Regions (IOI09_regions) C++17
0 / 100
 4252 ms 131072 KB 
// #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;
    vector<int> arr;

  public:
    BIT(int size) : size(size), bit(size + 1), arr(size) {}
    void set(int ind, int val) { add(ind, val - arr[ind]); }
    void add(int ind, int val) {
        arr[ind] += val;
        ind++;
        for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
    }
    int prev(int ind) {
        ind++;
        int total = 0;
        for (; 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]]]--;
    curr[nums[s]]--;
    en[s] = timer-1;
}
void getComp(int size){
    vector<int> b(size);
    for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
    for(int i = 0; i<b.size(); i++) for(int j: cnt[b[i]])
        sums[i].set(st[j], 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));
    getComp(p);
    BIT b(N);
    unordered_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.set(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.set(st[i], 0);
            mem[up*R+down] = ret;
           cout << ret << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'void dfs(int, std::vector<int>&)':
regions.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     else for(int i = 0; i<curr.size(); i++) ans[s][i] = curr[i];
      |                         ~^~~~~~~~~~~~
regions.cpp: In function 'void getComp(int)':
regions.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i<b.size(); i++) for(int j: cnt[b[i]])
      |                    ~^~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:83:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Runtime error 1 ms 464 KB Execution killed with signal 11
4 Runtime error 1 ms 464 KB Execution killed with signal 11
5 Runtime error 1 ms 464 KB Execution killed with signal 11
6 Runtime error 1 ms 592 KB Execution killed with signal 11
7 Runtime error 1 ms 720 KB Execution killed with signal 11
8 Runtime error 2 ms 848 KB Execution killed with signal 11
9 Runtime error 2 ms 1872 KB Execution killed with signal 11
10 Runtime error 4 ms 2384 KB Execution killed with signal 11
11 Runtime error 5 ms 3408 KB Execution killed with signal 11
12 Runtime error 8 ms 4432 KB Execution killed with signal 11
13 Runtime error 10 ms 4432 KB Execution killed with signal 11
14 Runtime error 316 ms 10768 KB Execution killed with signal 6
15 Runtime error 375 ms 16964 KB Execution killed with signal 6

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 32752 KB Execution killed with signal 6
2 Runtime error 53 ms 42280 KB Execution killed with signal 11
3 Runtime error 2567 ms 49476 KB Execution killed with signal 6
4 Runtime error 12 ms 6224 KB Execution killed with signal 11
5 Runtime error 13 ms 8032 KB Execution killed with signal 11
6 Runtime error 429 ms 44736 KB Execution killed with signal 6
7 Runtime error 931 ms 50700 KB Execution killed with signal 6
8 Runtime error 90 ms 131072 KB Execution killed with signal 9
9 Runtime error 52 ms 30524 KB Execution killed with signal 11
10 Runtime error 110 ms 131072 KB Execution killed with signal 9
11 Runtime error 68 ms 36300 KB Execution killed with signal 11
12 Runtime error 932 ms 62828 KB Execution killed with signal 11
13 Runtime error 201 ms 60500 KB Execution killed with signal 11
14 Runtime error 193 ms 131072 KB Execution killed with signal 11
15 Runtime error 4252 ms 81884 KB Execution killed with signal 6
16 Runtime error 394 ms 82672 KB Execution killed with signal 11
17 Runtime error 172 ms 131072 KB Execution killed with signal 6