oj.uz

답안 #727514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727514 2023-04-20T22:19:57 Z CutSandstone Regions (IOI09_regions) C++17
1 / 100
 179 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;
  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 block = sqrt(N);
    big.resize(R, -1);
    int p = 0;
    for(int i = 0; i<R; i++) if(cnt[i].size() >= block) 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;
        int get = mem[up*R+down];
        if(get) cout << get-1;
        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+1;
            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+1;
            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+1;
            cout << ret << endl;
        }
    }
}

Compilation message

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:67:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     for(int i = 0; i<R; i++) if(cnt[i].size() >= block) 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
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 336 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 336 KB Time limit exceeded (wall clock)
7 Execution timed out 5 ms 464 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 464 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 976 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 1232 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 1744 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 2512 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 2384 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 4688 KB Time limit exceeded (wall clock)
15 Execution timed out 31 ms 7632 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 34 ms 23388 KB Time limit exceeded (wall clock)
2 Execution timed out 33 ms 16484 KB Time limit exceeded (wall clock)
3 Execution timed out 33 ms 18564 KB Time limit exceeded (wall clock)
4 Execution timed out 108 ms 3836 KB Time limit exceeded (wall clock)
5 Execution timed out 52 ms 5452 KB Time limit exceeded (wall clock)
6 Execution timed out 35 ms 30972 KB Time limit exceeded (wall clock)
7 Execution timed out 50 ms 35664 KB Time limit exceeded (wall clock)
8 Execution timed out 84 ms 93900 KB Time limit exceeded (wall clock)
9 Execution timed out 131 ms 16636 KB Time limit exceeded (wall clock)
10 Runtime error 119 ms 131072 KB Execution killed with signal 9
11 Execution timed out 147 ms 18992 KB Time limit exceeded (wall clock)
12 Execution timed out 131 ms 27344 KB Time limit exceeded (wall clock)
13 Execution timed out 179 ms 27760 KB Time limit exceeded (wall clock)
14 Execution timed out 176 ms 56436 KB Time limit exceeded (wall clock)
15 Execution timed out 135 ms 32508 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 37952 KB Time limit exceeded (wall clock)
17 Execution timed out 117 ms 68816 KB Time limit exceeded (wall clock)