oj.uz

Submission #628289

# Submission time Handle Problem Language Result Execution time Memory
628289 2022-08-13T09:33:17 Z DeMen100ns Regions (IOI09_regions) C++17
100 / 100
 3422 ms 46436 KB 
/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc

Name: Regions
Sauce: https://oj.uz/problem/view/IOI09_regions
Tag: SQRT
Sol: 

//big - big/small : precal
//small - big/small : euler tour + binsearch
Note: 
*/

#include <bits/stdc++.h>

using namespace std;

template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } 
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

const int N = 2e5 + 5;
const long long INF = numeric_limits<long long>::max() / 2;
const int MAXA = 1e9;
const int B = sqrt(N);

vector <int> a[N], cnt[N], pos[N], node[N];
vector <int> euler;
int h[N], cntreg[N], sub[N], subp[N];

void dfs(int id, int u, int ct){
    for(int i : a[u]){
        cnt[id][h[i]] += ct;
        dfs(id, i, ct + (h[i] == id));
    }
}

void dfs_euler(int u){
    euler.push_back(u);
    for(int i : a[u]){
        dfs_euler(i);
        sub[u] += sub[i];
    }
    sub[u]++;
}

int get(vector <int> &v, int r){
    int k = upper_bound(v.begin(), v.end(), r) - v.begin();
    return k - 1;
}

void solve()
{
    int n, r, q; cin >> n >> r >> q;
    cin >> h[1]; 
    cntreg[h[1]] = 1; node[h[1]].push_back(1);
    for(int i = 2; i <= n; ++i){
        int u; cin >> u >> h[i];
        cntreg[h[i]]++;
        a[u].push_back(i);
        node[h[i]].push_back(i);
    }

    for(int i = 1; i <= r; ++i){
        if (cntreg[i] >= B){
            cnt[i].resize(r + 1);
            dfs(i, 1, (h[1] == i));
        }
    }
    dfs_euler(1);
    for(int i = 0; i < n; ++i){
        pos[h[euler[i]]].push_back(i + 1);
        subp[i + 1] = sub[euler[i]];
    }
    while (q--){
        int h1, h2;
        cin >> h1 >> h2;

        if (cntreg[h1] >= B){
            cout << cnt[h1][h2] << endl;
        } else {
            int ans = 0;
            for(int i : pos[h1]){
                ans += get(pos[h2], i + subp[i] - 1) - get(pos[h2], i - 1);
            }
            cout << ans << endl;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    int t = 1; //cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct
2 Correct 11 ms 19096 KB Output is correct
3 Correct 12 ms 19024 KB Output is correct
4 Correct 18 ms 19068 KB Output is correct
5 Correct 17 ms 19152 KB Output is correct
6 Correct 25 ms 19204 KB Output is correct
7 Correct 32 ms 19152 KB Output is correct
8 Correct 36 ms 19152 KB Output is correct
9 Correct 50 ms 19764 KB Output is correct
10 Correct 83 ms 19664 KB Output is correct
11 Correct 115 ms 20048 KB Output is correct
12 Correct 138 ms 20560 KB Output is correct
13 Correct 176 ms 20168 KB Output is correct
14 Correct 145 ms 20816 KB Output is correct
15 Correct 206 ms 24012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 24476 KB Output is correct
2 Correct 2007 ms 22976 KB Output is correct
3 Correct 2824 ms 26972 KB Output is correct
4 Correct 305 ms 20880 KB Output is correct
5 Correct 298 ms 22888 KB Output is correct
6 Correct 763 ms 24064 KB Output is correct
7 Correct 1387 ms 24152 KB Output is correct
8 Correct 1214 ms 34436 KB Output is correct
9 Correct 2244 ms 29516 KB Output is correct
10 Correct 3181 ms 42708 KB Output is correct
11 Correct 3422 ms 29344 KB Output is correct
12 Correct 1396 ms 30788 KB Output is correct
13 Correct 1848 ms 31448 KB Output is correct
14 Correct 2603 ms 32568 KB Output is correct
15 Correct 2647 ms 37444 KB Output is correct
16 Correct 2475 ms 46436 KB Output is correct
17 Correct 2292 ms 46124 KB Output is correct