oj.uz

Submission #595398

# Submission time Handle Problem Language Result Execution time Memory
595398 2022-07-13T17:17:23 Z Do_you_copy Regions (IOI09_regions) C++17
100 / 100
 5942 ms 62368 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
 
ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}
 
ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}
 
//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 3e5 + 1;
const int maxR = 25000 + 1;
int n, r, q, sq;
vector <int> color[maxR];
vector <int> adj[maxN];
vector <vector<ll>> cnt, rcnt;
int pos[maxN], be[maxN], child[maxN];
int dpos[maxN], time_in;
int bit[maxN];
 
void update(int x, int val){
    for (; x <= n; x += x & -x){
        bit[x] += val;
    }
}
 
int get(int x){
    int sum = 0;
    for (; x; x -= x & -x){
        sum += bit[x];
    }
    return sum;
}
 
void pre_dfs(int u){
    dpos[u] = ++time_in;
    for (const int &i: adj[u]){
        pre_dfs(i);
        child[u] += child[i] + 1;
    }
}
 
int dfs(int u, int c, int up = 0){
    ll summ = 0;
    if (be[u] == c) ++up;
    else rcnt[rcnt.size() - 1][be[u]] += up;
    for (const int &i: adj[u]){
        summ += dfs(i, c, up);
    }
    if (be[u] == c) return summ + 1;
    cnt[cnt.size() - 1][be[u]] += summ;
    return summ;
}
 
void Init(){
    cin >> n >> r >> q;
    sq = sqrt(n) + 1;
    int t; cin >> t;
    be[1] = t;
    color[t].pb(1);
    for (int i = 2; i <= n; ++i){
        int p, t;
        cin >> p >> t;
        color[t].pb(i);
        be[i] = t;
        adj[p].pb(i);
    }
    pre_dfs(1);
    for (int i = 1; i <= r; ++i){
        if (color[i].size() >= sq){
            pos[i] = cnt.size();
            cnt.pb({});
            rcnt.pb({});
            cnt.back().resize(maxR, 0);
            rcnt.back().resize(maxR, 0);
            dfs(1, i);
        }
    }
    for (int i = 1; i <= q; ++i){
        int u, v;
        cin >> u >> v;
        if (color[v].size() >= sq){
            cout << cnt[pos[v]][u] << endl;
        }
        else if (color[u].size() >= sq){
            cout << rcnt[pos[u]][v] << endl;
        }
        else{
            for (const int &i: color[v]){
                update(dpos[i], 1);
            }
            ll ans = 0;
            for (const int &i: color[u]){
                ans += get(dpos[i] + child[i]) - get(dpos[i]);
            }
            cout << ans << endl;
            for (const int &i: color[v]){
                update(dpos[i], -1);
            }
        }
    }
}
 
 
int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

regions.cpp: In function 'void Init()':
regions.cpp:86:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (color[i].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         if (color[v].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:101:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         else if (color[u].size() >= sq){
      |                  ~~~~~~~~~~~~~~~~^~~~~
regions.cpp: In function 'int main()':
regions.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8392 KB Output is correct
2 Correct 4 ms 7888 KB Output is correct
3 Correct 12 ms 7888 KB Output is correct
4 Correct 11 ms 7856 KB Output is correct
5 Correct 14 ms 7888 KB Output is correct
6 Correct 18 ms 8064 KB Output is correct
7 Correct 29 ms 8016 KB Output is correct
8 Correct 39 ms 8144 KB Output is correct
9 Correct 49 ms 8400 KB Output is correct
10 Correct 92 ms 8396 KB Output is correct
11 Correct 111 ms 8716 KB Output is correct
12 Correct 131 ms 9228 KB Output is correct
13 Correct 277 ms 8792 KB Output is correct
14 Correct 361 ms 10660 KB Output is correct
15 Correct 481 ms 13024 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1562 ms 21748 KB Output is correct
2 Correct 1688 ms 16456 KB Output is correct
3 Correct 3109 ms 18764 KB Output is correct
4 Correct 361 ms 9488 KB Output is correct
5 Correct 428 ms 11088 KB Output is correct
6 Correct 631 ms 34412 KB Output is correct
7 Correct 1057 ms 31472 KB Output is correct
8 Correct 1304 ms 56996 KB Output is correct
9 Correct 3851 ms 16704 KB Output is correct
10 Correct 2956 ms 62368 KB Output is correct
11 Correct 5942 ms 16384 KB Output is correct
12 Correct 1777 ms 19008 KB Output is correct
13 Correct 2358 ms 19440 KB Output is correct
14 Correct 2394 ms 26812 KB Output is correct
15 Correct 4229 ms 24040 KB Output is correct
16 Correct 4403 ms 31480 KB Output is correct
17 Correct 3758 ms 38264 KB Output is correct