oj.uz

Submission #744202

# Submission time Handle Problem Language Result Execution time Memory
744202 2023-05-18T09:11:52 Z hafo Regions (IOI09_regions) C++14
100 / 100
 4647 ms 32824 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;
const int sz = 450 + 7;
const int m = 25e3 + 7;

int n, st[maxn], en[maxn], timer = 0, r, q, home[maxn], cnt[maxn], r1, r2, f[sz][m], mp[m];
vector<int> g[maxn], tp[m], cp[m], large;

void dfs(int u, int par) {
    st[u] = ++timer;
    cp[home[u]].pb(timer);
    for(int i = 0; i < large.size(); i++) f[i][home[u]] += mp[large[i]];

    for(auto v:g[u]) {
        if(v == par) continue;
        mp[home[v]]++;
        dfs(v, u);
        mp[home[v]]--;
    }
    en[u] = timer;
}

int get(int l, int r, int col) {
    return upper_bound(all(cp[col]), r) - lower_bound(all(cp[col]), l);
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>r>>q;
    cin>>home[1];
    cnt[home[1]]++;
    for(int i = 2; i <= n; i++) {
        int x;
        cin>>x>>home[i];
        cnt[home[i]]++;
        g[x].pb(i);
    }

    mp[home[1]]++;
    for(int i = 1; i <= n; i++)
        if(cnt[home[i]] <= sz) tp[home[i]].pb(i);
    for(int i = 1; i <= r; i++)
        if(cnt[i] > sz) large.pb(i);
    dfs(1, 0);
    while(q--) {
        cin>>r1>>r2;
        if(cnt[r1] <= sz) {
            int ans = 0;
            for(auto u:tp[r1]) {
                ans += get(st[u], en[u], r2) - (r1 == r2);
            }
            cout<<ans<<endl;
        } else {
            int id = lower_bound(all(large), r1) - large.begin();
            cout<<f[id][r2]<<endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < large.size(); i++) f[i][home[u]] += mp[large[i]];
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 7 ms 6096 KB Output is correct
5 Correct 7 ms 6224 KB Output is correct
6 Correct 13 ms 6224 KB Output is correct
7 Correct 32 ms 6224 KB Output is correct
8 Correct 39 ms 6224 KB Output is correct
9 Correct 50 ms 6864 KB Output is correct
10 Correct 80 ms 6736 KB Output is correct
11 Correct 129 ms 7040 KB Output is correct
12 Correct 149 ms 7668 KB Output is correct
13 Correct 190 ms 7120 KB Output is correct
14 Correct 302 ms 7772 KB Output is correct
15 Correct 265 ms 11464 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1665 ms 11188 KB Output is correct
2 Correct 2127 ms 9540 KB Output is correct
3 Correct 2838 ms 13480 KB Output is correct
4 Correct 277 ms 7880 KB Output is correct
5 Correct 341 ms 10300 KB Output is correct
6 Correct 550 ms 11052 KB Output is correct
7 Correct 1581 ms 10824 KB Output is correct
8 Correct 944 ms 21468 KB Output is correct
9 Correct 2761 ms 16196 KB Output is correct
10 Correct 4432 ms 26660 KB Output is correct
11 Correct 4647 ms 15744 KB Output is correct
12 Correct 1483 ms 17016 KB Output is correct
13 Correct 1990 ms 17736 KB Output is correct
14 Correct 2061 ms 18816 KB Output is correct
15 Correct 3229 ms 23692 KB Output is correct
16 Correct 2814 ms 32824 KB Output is correct
17 Correct 2828 ms 32284 KB Output is correct