oj.uz

Submission #743837

# Submission time Handle Problem Language Result Execution time Memory
743837 2023-05-18T04:40:26 Z hafo Regions (IOI09_regions) C++14
35 / 100
 4758 ms 36980 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;
bool fir[maxn];

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[home[i]];

    for(auto v:g[u]) {
        if(v == par) continue;
        if(!mp[home[v]]) fir[v] = 1;
        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]]++;
    fir[1] = 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);
            }
            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:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < large.size(); i++) f[i][home[u]] += mp[home[i]];
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10192 KB Output is correct
2 Correct 7 ms 10192 KB Output is correct
3 Correct 10 ms 10320 KB Output is correct
4 Correct 10 ms 10320 KB Output is correct
5 Correct 14 ms 10320 KB Output is correct
6 Correct 22 ms 10320 KB Output is correct
7 Correct 41 ms 10320 KB Output is correct
8 Correct 44 ms 10448 KB Output is correct
9 Correct 32 ms 10960 KB Output is correct
10 Correct 107 ms 10832 KB Output is correct
11 Correct 138 ms 11156 KB Output is correct
12 Correct 182 ms 11684 KB Output is correct
13 Correct 150 ms 11416 KB Output is correct
14 Correct 340 ms 11900 KB Output is correct
15 Correct 285 ms 15652 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1808 ms 15316 KB Output isn't correct
2 Incorrect 2145 ms 13740 KB Output isn't correct
3 Incorrect 3226 ms 17620 KB Output isn't correct
4 Correct 283 ms 12108 KB Output is correct
5 Correct 348 ms 14416 KB Output is correct
6 Incorrect 407 ms 15140 KB Output isn't correct
7 Incorrect 1462 ms 14980 KB Output isn't correct
8 Incorrect 1139 ms 25600 KB Output isn't correct
9 Correct 2508 ms 20580 KB Output is correct
10 Incorrect 4019 ms 30880 KB Output isn't correct
11 Correct 4758 ms 20028 KB Output is correct
12 Incorrect 1676 ms 21312 KB Output isn't correct
13 Incorrect 2188 ms 21896 KB Output isn't correct
14 Incorrect 2346 ms 23056 KB Output isn't correct
15 Incorrect 3224 ms 27940 KB Output isn't correct
16 Incorrect 2914 ms 36980 KB Output isn't correct
17 Incorrect 3279 ms 36528 KB Output isn't correct