oj.uz

Submission #743840

# Submission time Handle Problem Language Result Execution time Memory
743840 2023-05-18T04:48:50 Z hafo Regions (IOI09_regions) C++14
50 / 100
 4519 ms 36680 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, a[maxn], r, q, home[maxn], cnt[maxn], r1, r2, f[sz][m], mp[sz];
vector<int> g[maxn], tp[maxn], 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 5 ms 10196 KB Output is correct
2 Correct 6 ms 10304 KB Output is correct
3 Correct 7 ms 10248 KB Output is correct
4 Correct 9 ms 10320 KB Output is correct
5 Correct 12 ms 10320 KB Output is correct
6 Correct 21 ms 10324 KB Output is correct
7 Correct 31 ms 10320 KB Output is correct
8 Correct 34 ms 10320 KB Output is correct
9 Correct 81 ms 10960 KB Output is correct
10 Correct 97 ms 10832 KB Output is correct
11 Correct 128 ms 11064 KB Output is correct
12 Correct 174 ms 11780 KB Output is correct
13 Correct 229 ms 11344 KB Output is correct
14 Correct 347 ms 11892 KB Output is correct
15 Correct 287 ms 15688 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 15308 KB Output is correct
2 Correct 2043 ms 13624 KB Output is correct
3 Correct 2608 ms 17596 KB Output is correct
4 Correct 340 ms 12040 KB Output is correct
5 Correct 439 ms 14392 KB Output is correct
6 Incorrect 518 ms 15084 KB Output isn't correct
7 Incorrect 1746 ms 14892 KB Output isn't correct
8 Incorrect 1221 ms 25540 KB Output isn't correct
9 Correct 2782 ms 20324 KB Output is correct
10 Incorrect 4161 ms 30680 KB Output isn't correct
11 Correct 4519 ms 19864 KB Output is correct
12 Incorrect 1603 ms 21020 KB Output isn't correct
13 Incorrect 2068 ms 21728 KB Output isn't correct
14 Incorrect 2414 ms 22852 KB Output isn't correct
15 Incorrect 3342 ms 27708 KB Output isn't correct
16 Incorrect 2990 ms 36680 KB Output isn't correct
17 Incorrect 2830 ms 36324 KB Output isn't correct