oj.uz

Submission #1043577

# Submission time Handle Problem Language Result Execution time Memory
1043577 2024-08-04T11:36:21 Z Azm1t Regions (IOI09_regions) C++17
0 / 100
 8000 ms 36176 KB 
#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for (long long i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()

// #define int long long
#define double long double
const long long inf = (long long) 1e18;
const int mod = (int) 998244353;

signed main(){

    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout << fixed << setprecision(10);

    int n, r, q; cin >> n >> r >> q;
    vector<vector<int>> adj(n);

    vector<int> color[r];
    vector<int> region(n);
    vector<int> regiontotime[r];
    cin >> region[0]; region[0]--;
    color[region[0]].push_back(0);

    rep(i, 1, n){
        int y; cin >> y >> region[i];
        y--; region[i]--;
        adj[y].push_back(i);
        color[region[i]].push_back(i);
    }

    vector<int> pc;
    rep(i, 0, r) if(sz(color[i])*sz(color[i]) >= n) pc.push_back(i);

    map<pair<int, int>, int> precomp;
    vector<int> in(n, 0), out(n, 0), szz(n, 1);
    int time = 0;

    function<void(int, int)> dfs = [&](int v, int p){
        in[v] = time++;
        regiontotime[region[v]].push_back(in[v]);
        for(auto child: adj[v]){
            dfs(child, v);
            szz[v] += szz[child];
        }
        out[v] = time++;
    };

    dfs(0, -1);

    for(auto u: pc){
        for(auto v: pc){
            if(u == v) continue;
            for(auto val: color[u]){
                precomp[{u, v}] += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
            }
        }
    }

    while(q--){
        int u, v; cin >> u >> v; u--; v--;
        if(precomp.find({u, v}) != precomp.end()) cout << precomp[{u, v}] << endl;
        else{
            int res = 0;
            for(auto val: color[u]) res += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
            cout << res << endl;
        }
    }

    
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Incorrect 2 ms 344 KB Output isn't correct
5 Incorrect 4 ms 344 KB Output isn't correct
6 Incorrect 5 ms 344 KB Output isn't correct
7 Incorrect 16 ms 344 KB Output isn't correct
8 Incorrect 16 ms 600 KB Output isn't correct
9 Incorrect 29 ms 1112 KB Output isn't correct
10 Incorrect 41 ms 1112 KB Output isn't correct
11 Incorrect 76 ms 1624 KB Output isn't correct
12 Incorrect 79 ms 2392 KB Output isn't correct
13 Incorrect 109 ms 2132 KB Output isn't correct
14 Incorrect 177 ms 2904 KB Output isn't correct
15 Incorrect 191 ms 7580 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 7593 ms 7832 KB Output isn't correct
2 Execution timed out 8007 ms 6068 KB Time limit exceeded
3 Incorrect 7925 ms 10984 KB Output isn't correct
4 Incorrect 202 ms 3200 KB Output isn't correct
5 Incorrect 269 ms 6224 KB Output isn't correct
6 Incorrect 595 ms 5572 KB Output isn't correct
7 Incorrect 1210 ms 7184 KB Output isn't correct
8 Incorrect 1501 ms 16416 KB Output isn't correct
9 Incorrect 1886 ms 15588 KB Output isn't correct
10 Incorrect 3187 ms 25472 KB Output isn't correct
11 Incorrect 2803 ms 16532 KB Output isn't correct
12 Execution timed out 8041 ms 17032 KB Time limit exceeded
13 Execution timed out 8053 ms 18000 KB Time limit exceeded
14 Execution timed out 8051 ms 17744 KB Time limit exceeded
15 Execution timed out 8077 ms 25424 KB Time limit exceeded
16 Execution timed out 8070 ms 36176 KB Time limit exceeded
17 Execution timed out 8004 ms 33796 KB Time limit exceeded