oj.uz

Submission #595397

# Submission time Handle Problem Language Result Execution time Memory
595397 2022-07-13T17:16:23 Z Do_you_copy Regions (IOI09_regions) C++17
100 / 100
 6550 ms 73956 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 <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
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 ll maxN = 3e5 + 1;
const ll maxR = 3e4;
ll n, r, q, sq;
vector <ll> color[maxR];
vector <ll> adj[maxN];
vector <vector<ll>> cnt, rcnt;
ll pos[maxN], be[maxN], child[maxN];
ll dpos[maxN], time_in;
ll bit[maxN];

void update(ll x, ll val){
    for (; x <= n; x += x & -x){
        bit[x] += val;
    }
}

ll get(ll x){
    ll sum = 0;
    for (; x; x -= x & -x){
        sum += bit[x];
    }
    return sum;
}

void pre_dfs(ll u){
    dpos[u] = ++time_in;
    for (const ll &i: adj[u]){
        pre_dfs(i);
        child[u] += child[i] + 1;
    }
}

ll dfs(ll u, ll c, ll up = 0){
    ll summ = 0;
    if (be[u] == c) ++up;
    else rcnt[rcnt.size() - 1][be[u]] += up;
    for (const ll &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;
    ll t; cin >> t;
    be[1] = t;
    color[t].pb(1);
    for (ll i = 2; i <= n; ++i){
        ll p, t;
        cin >> p >> t;
        color[t].pb(i);
        be[i] = t;
        adj[p].pb(i);
    }
    pre_dfs(1);
    for (ll 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 (ll i = 1; i <= q; ++i){
        ll 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 ll &i: color[v]){
                update(dpos[i], 1);
            }
            ll ans = 0;
            for (const ll &i: color[u]){
                ans += get(dpos[i] + child[i]) - get(dpos[i]);
            }
            cout << ans << endl;
            for (const ll &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<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   86 |         if (color[i].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   98 |         if (color[v].size() >= sq){
      |             ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:101:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8528 KB Output is correct
2 Correct 4 ms 8016 KB Output is correct
3 Correct 6 ms 8016 KB Output is correct
4 Correct 10 ms 8016 KB Output is correct
5 Correct 13 ms 8144 KB Output is correct
6 Correct 24 ms 8144 KB Output is correct
7 Correct 44 ms 8144 KB Output is correct
8 Correct 33 ms 8256 KB Output is correct
9 Correct 53 ms 8616 KB Output is correct
10 Correct 58 ms 8720 KB Output is correct
11 Correct 163 ms 9176 KB Output is correct
12 Correct 104 ms 9796 KB Output is correct
13 Correct 230 ms 9608 KB Output is correct
14 Correct 381 ms 11652 KB Output is correct
15 Correct 376 ms 14112 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 25240 KB Output is correct
2 Correct 1715 ms 19424 KB Output is correct
3 Correct 3283 ms 21504 KB Output is correct
4 Correct 296 ms 10200 KB Output is correct
5 Correct 463 ms 11976 KB Output is correct
6 Correct 569 ms 40440 KB Output is correct
7 Correct 1193 ms 37052 KB Output is correct
8 Correct 1440 ms 67200 KB Output is correct
9 Correct 4111 ms 20116 KB Output is correct
10 Correct 2961 ms 73956 KB Output is correct
11 Correct 6550 ms 21016 KB Output is correct
12 Correct 1960 ms 23128 KB Output is correct
13 Correct 2589 ms 23632 KB Output is correct
14 Correct 3094 ms 32884 KB Output is correct
15 Correct 4868 ms 28216 KB Output is correct
16 Correct 5717 ms 35520 KB Output is correct
17 Correct 4870 ms 44248 KB Output is correct