oj.uz

Submission #447174

# Submission time Handle Problem Language Result Execution time Memory
447174 2021-07-25T00:16:41 Z SirCovidThe19th Regions (IOI09_regions) C++14
100 / 100
 4588 ms 49128 KB 
#include <bits/stdc++.h>
using namespace std; 

#define lb(x, v) lower_bound(x.begin(), x.end(), v)

const int mN = 2e5+5, mR = 25005;

int n, r, q, R[mN], tin[mN], tout[mN], ti = 0, cntReg[mR]; 
vector<int> adj[mN], reg[mR], pos[mR]; vector<pair<int, int>> trav[mR]; 
map<pair<int, int>, int> store;

void dfs(int i){
    cntReg[R[i]]++; pos[R[i]].push_back(tin[i] = ti++);
    trav[R[i]].push_back({tin[i], cntReg[R[i]]});
    for (int x : adj[i]) dfs(x);
    trav[R[i]].push_back({ti, cntReg[R[i]]-1});
    cntReg[R[i]]--; tout[i] = ti-1; 
}

int main(){
    cin >> n >> r >> q; 
    for (int i = 1; i <= n; i++){
        if (i == 1) cin >> R[i];
        else{ int p; cin >> p >> R[i]; adj[p].push_back(i); }
        reg[R[i]].push_back(i);
    }dfs(1);
    while (q--){
        int a, b, ans = 0; bool swp = 0; cin >> a >> b;
        if (store.count({a, b})){ cout<<store[{a, b}]<<endl; continue; }
        if (reg[a].size() > reg[b].size()) swap(a, b), swp = 1;
        for (int x : reg[a]){
            if (swp){
                auto it = lb(trav[b], make_pair(tin[x], INT_MAX));
                if (it != trav[b].begin()) ans += prev(it)->second;
            }else ans += lb(pos[b], tout[x]+1)-lb(pos[b], tin[x]);
        }if (swp){ swap(a, b); } store[{a, b}] = ans; cout<<ans<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 4 ms 6728 KB Output is correct
3 Correct 5 ms 6728 KB Output is correct
4 Correct 10 ms 6796 KB Output is correct
5 Correct 12 ms 6852 KB Output is correct
6 Correct 31 ms 6956 KB Output is correct
7 Correct 42 ms 7052 KB Output is correct
8 Correct 50 ms 7032 KB Output is correct
9 Correct 49 ms 7836 KB Output is correct
10 Correct 91 ms 7896 KB Output is correct
11 Correct 149 ms 8512 KB Output is correct
12 Correct 194 ms 9296 KB Output is correct
13 Correct 256 ms 9096 KB Output is correct
14 Correct 321 ms 9920 KB Output is correct
15 Correct 277 ms 14176 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 15100 KB Output is correct
2 Correct 1617 ms 13628 KB Output is correct
3 Correct 2426 ms 20076 KB Output is correct
4 Correct 299 ms 10732 KB Output is correct
5 Correct 515 ms 13796 KB Output is correct
6 Correct 695 ms 13012 KB Output is correct
7 Correct 858 ms 13816 KB Output is correct
8 Correct 1326 ms 24100 KB Output is correct
9 Correct 2716 ms 29048 KB Output is correct
10 Correct 3740 ms 37624 KB Output is correct
11 Correct 4588 ms 32816 KB Output is correct
12 Correct 1745 ms 26612 KB Output is correct
13 Correct 2526 ms 29592 KB Output is correct
14 Correct 3091 ms 30544 KB Output is correct
15 Correct 4553 ms 39588 KB Output is correct
16 Correct 4336 ms 49128 KB Output is correct
17 Correct 4403 ms 46860 KB Output is correct